本文共 1141 字，大约阅读时间需要 3 分钟。

答案必定是某个割点,但是割点并不一定是答案

移除割点后,原图被分成若干个部分,如何判断$a,b$在不同的连通块??

我们知道,我们认定$u$是割点是因为存在

$$dfn[u]<=low[v]$$

此时$v$的子树无法回到更浅的节点,割掉$u$,将与其他部分丧失联系

如果$b$在$v$的子树内,那么$u$必定是答案之一

$b$在子树内必然有$dfn[b]>=dfn[v]$,判断下即可

#include 
   
    using namespace std;const int maxn = 1e6+19;struct edge{
   	int to,nxt;}d[maxn]; int head[maxn],cnt=1;void add(int u,int v){
    d[++cnt] = ( edge ){
   v,head[u]},head[u] = cnt; }int n,low[maxn],dfn[maxn],cut[maxn],vis[maxn],a,b,id;void tarjan(int u,int fa){
   	dfn[u] = low[u] = ++id; int child = 0;	for(int i=head[u];i;i=d[i].nxt )	{
   		int v = d[i].to;		if( !dfn[v] )		{
   			tarjan(v,fa); child++;			low[u] = min( low[u],low[v] );			if( u!=fa && dfn[u]<=low[v] )			{
   				cut[u] = 1;//是割点 				if( dfn[b]>=dfn[v] )	vis[u] = 1;			}		}		else	low[u] = min( low[u],dfn[v] );	}	if( u==fa && child>=2 )	cut[u] = 1;}int main(){
   	cin >> n; int l,r;	while( cin >> l >> r && (l+r) )	add(l,r),add(r,l);	cin >> a >> b;	tarjan(a,a);	for(int i=1;i<=n;i++)		if( vis[i] )	{
    cout << i; return 0; }	cout << "No solution";}
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/115286750 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！