tarjan算法强连通分量的正确性解释+错误更新方法的解释！！！+hdu1269
- 2020 年 3 月 28 日
- 筆記
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1269
以下内容为原创，转载请声明。
强连通分量SCC（Strongly Connected Component）：一个图的子图，如果任何两个点都互相可达且满足最大性，该子图就是原图的SCC。
对于有向图的连通性，tarjan可以说是十分牛逼了，由于tarjan只需要一次dfs就能判断有向图中所有的SCC，所以他的复杂度是O(|V|+|E|)，也就是把每条边和每个点都会检索一遍，是在线性时间能处理出所有的SCC的！下面简单说明求强连通分量的tarjan算法的过程以及正确性。
基础知识：
①、经dfs处理过的点的low值相同的一定属于同一个SCC，这个SCC中第一个被dfs访问的点也就是dfn=low的点一定就是这个SCC中每个点的low值，显而易见。
②、在dfs过程中，dfs进行最深处一定会进入某一个SCC，（尽管在过程中可能会进入其他SCC），下面我会解释
③、标记SCC Number的过程可以用栈实现，因为dfs的过程就是递归，递归和栈非常相似
tarjan算法的流程：将每个访问的点入栈，更新low值，直到到达一个点，这个点low值等于dfn值，说明这个点一定是一个SCC的祖先，也就是第一个访问的点，此时这个点一定在栈的底部！！因为是通过dfs退出多次而不弹栈才得到这个low=dfn。我们只要不断弹出l这个SCC的点并标记就可以，直到弹到栈底。我们先看基础知识（2），上图中在访问3的时候进入了4、5结点，也就是其他SCC，到了5的时候，由于low[5]=dfn[5]所以此时弹栈，发现就只有一个5属于这个SCC，4也是同样的过程，直到到了3，进入另一个分支6，这就是我基础知识（2）中的一定会在最终进入一个SCC而且栈底元素就是这个SCC的祖结点。
关于强连通分量处理回退边的方式，我的解释是这样的：
当一个点已经标记过dfn之后，而且这个点在之前没有标记过SCC（因为在dfs过程中会进入并处理其他SCC，若此时有边相连就无需更新，因为回退边所到点的low值一定小于该点的low)就用
①、low[u]=min(low[v],dfn[v]) ②、low[u]=min(low[v],low[u])
来更新low值，其实对于双连通分量来说，这两种更新方式的结果是一样的，但是第一种方法在原理上是错误的！！！！！ 我来举一个例子，又是下面这张图，
对于第一种我们得出的结果是下面第一张图，而对于第二张我们得到的结果是下面第二张图，我们可以发现，根据tarjan算法的思想，处于同一个强连通分量中的点low值应该是相同的，但是第一种做法中的点的low值是不同的，但是他们得到的结果都是一样的，都是图是强连通的，为什么呢？
下面我将证明第一种做法得出正确结果的原因：
由于对于4,5号节点来说，他们的low值为3的时候，都与他们的dfn值不相同（dfn[4]=4&dfn[5]=5），所以他们就会一直在栈中，而栈底也一定是1号结点。4,5号结点没有机会弹出，直到dfs return到1号结点，此时才会弹栈，一直到弹出1号结点为止，这就把栈中的结点4,5弹出了，但是事实上他们的low值是更新错误的。尽管是错误的，但是中途dfs在访问其他SCC的时候（如果有的话，可以参考最上面那张图）已经把其他SCC的点都标记了，此时栈中剩下的只有这一个SCC！！所以最终的结果是相同的，但是！！这种更新方法是错误的！！因为在之后不能通过他们的不同的low值数量去查看SCC的数量，只能从每一次弹栈中给出的SCCNUMBER中得到SCC的信息。而且，这种做法跟tarjan的算法中“每个SCC”的low值是相同的是矛盾的。
看完我的文章能不能支持一下呢
hdu1269代码如下：
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef unsigned int ui; 4 typedef long long ll; 5 typedef unsigned long long ull; 6 #define pf printf 7 #define mem(a,b) memset(a,b,sizeof(a)) 8 #define prime1 1e9+7 9 #define prime2 1e9+9 10 #define pi 3.14159265 11 #define lson l,mid,rt<<1 12 #define rson mid+1,r,rt<<1|1 13 #define scand(x) scanf("%llf",&x) 14 #define f(i,a,b) for(int i=a;i<=b;i++) 15 #define scan(a) scanf("%d",&a) 16 #define mp(a,b) make_pair((a),(b)) 17 #define P pair<int,int> 18 #define dbg(args) cout<<#args<<":"<<args<<endl; 19 #define inf 0x3f3f3f3f 20 inline int read(){ 21 int ans=0,w=1; 22 char ch=getchar(); 23 while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();} 24 while(isdigit(ch))ans=(ans<<3)+(ans<<1)+ch-'0',ch=getchar(); 25 return ans*w; 26 } 27 const int maxn=1e5+10; 28 int n,m,t; 29 int head[maxn],nxt[maxn],low[maxn],sccno[maxn],dfn[maxn],id; 30 struct node{ 31 int u,v; 32 }p[maxn*10]; 33 int e=0; 34 int cnt; 35 stack<int> sk; 36 void addedge(int u,int v) 37 { 38 p[e].u=u; 39 p[e].v=v; 40 nxt[e]=head[u]; 41 head[u]=e++; 42 } 43 void tarjan(int u) 44 { 45 low[u]=dfn[u]=++id; 46 sk.push(u);//将结点编号压栈 47 for(int i=head[u];~i;i=nxt[i]) 48 { 49 int v=p[i].v; 50 if(!dfn[v]) 51 { 52 tarjan(v); 53 low[u]=min(low[u],low[v]); 54 } 55 else if(!sccno[v])//回退边且边终点没有标记SCC 56 low[u]=min(low[u],low[v]); 57 } 58 if(low[u]==dfn[u]) 59 { 60 cnt++;//连通分量的数量增加,对每个点这个if语句只执行一次 61 while(1) 62 { 63 int v=sk.top(); 64 sk.pop(); 65 sccno[v]=cnt; 66 if(u==v)break; 67 } 68 } 69 } 70 int main() 71 { 72 freopen("input.txt","r",stdin); 73 //freopen("output.txt","w",stdout); 74 std::ios::sync_with_stdio(false); 75 while(scanf("%d%d",&n,&m)==2) 76 { 77 if(n==0&&m==0)break; 78 e=0;cnt=0; 79 mem(head,-1);mem(nxt,-1); 80 while(!sk.empty())sk.pop(); 81 int x,y; 82 f(i,1,m) 83 { 84 x=read(); 85 y=read(); 86 addedge(x,y); 87 } 88 mem(dfn,0); 89 id=0; 90 mem(sccno,0); 91 mem(low,0); 92 f(i,1,n) 93 { 94 if(!dfn[i]) 95 tarjan(i); 96 } 97 f(i,1,n)dbg(low[i]); 98 if(cnt==1)pf("Yesn"); 99 else pf("Non"); 100 } 101 }
