题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=1269
以下内容为原创, 转载请声明.
强连通分量 SCC(Strongly Connected Component): 一个图的子图, 如果任何两个点都互相可达且满足最大性, 该子图就是原图的 SCC.
对于有向图的连通性, tarjan 可以说是十分牛逼了, 由于 tarjan 只需要一次 dfs 就能判断有向图中所有的 SCC, 所以他的复杂度是 O(|V|+|E|), 也就是把每条边和每个点都会检索一遍, 是在线性时间能处理出所有的 SCC 的! 下面简单说明求强连通分量的 tarjan 算法的过程以及正确性.
基础知识:
1, 经 dfs 处理过的点的 low 值相同的一定属于同一个 SCC, 这个 SCC 中第一个被 dfs 访问的点也就是 dfn=low 的点一定就是这个 SCC 中每个点的 low 值, 显而易见.
2, 在 dfs 过程中, dfs 进行最深处一定会进入某一个 SCC,(尽管在过程中可能会进入其他 SCC), 下面我会解释
3, 标记 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)就用
1,low[u]=min(low[v],dfn[v]) 2,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 代码如下:
- #include<bits/stdc++.h>
- using namespace std;
- typedef unsigned int ui;
- typedef long long ll;
- typedef unsigned long long ull;
- #define pf printf
- #define mem(a,b) memset(a,b,sizeof(a))
- #define prime1 1e9+7
- #define prime2 1e9+9
- #define pi 3.14159265
- #define lson l,mid,rt<<1
- #define rson mid+1,r,rt<<1|1
- #define scand(x) scanf("%llf",&x)
- #define f(i,a,b) for(int i=a;i<=b;i++)
- #define scan(a) scanf("%d",&a)
- #define mp(a,b) make_pair((a),(b))
- #define P pair<int,int>
- #define dbg(args) cout<<#args<<":"<<args<<endl;
- #define inf 0x3f3f3f3f
- inline int read(){
- int ans=0,w=1;
- char ch=getchar();
- while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
- while(isdigit(ch))ans=(ans<<3)+(ans<<1)+ch-'0',ch=getchar();
- return ans*w;
- }
- const int maxn=1e5+10;
- int n,m,t;
- int head[maxn],nxt[maxn],low[maxn],sccno[maxn],dfn[maxn],id;
- struct node{
- int u,v;
- }p[maxn*10];
- int e=0;
- int cnt;
- stack<int> sk;
- void addedge(int u,int v)
- {
- p[e].u=u;
- p[e].v=v;
- nxt[e]=head[u];
- head[u]=e++;
- }
- void tarjan(int u)
- {
- low[u]=dfn[u]=++id;
- sk.push(u);// 将结点编号压栈
- for(int i=head[u];~i;i=nxt[i])
- {
- int v=p[i].v;
- if(!dfn[v])
- {
- tarjan(v);
- low[u]=min(low[u],low[v]);
- }
- else if(!sccno[v])// 回退边且边终点没有标记 SCC
- low[u]=min(low[u],low[v]);
- }
- if(low[u]==dfn[u])
- {
- cnt++;// 连通分量的数量增加, 对每个点这个 if 语句只执行一次
- while(1)
- {
- int v=sk.top();
- sk.pop();
- sccno[v]=cnt;
- if(u==v)break;
- }
- }
- }
- int main()
- {
- freopen("input.txt","r",stdin);
- //freopen("output.txt","w",stdout);
- std::iOS::sync_with_stdio(false);
- while(scanf("%d%d",&n,&m)==2)
- {
- if(n==0&&m==0)break;
- e=0;cnt=0;
- mem(head,-1);mem(nxt,-1);
- while(!sk.empty())sk.pop();
- int x,y;
- f(i,1,m)
- {
- x=read();
- y=read();
- addedge(x,y);
- }
- mem(dfn,0);
- id=0;
- mem(sccno,0);
- mem(low,0);
- f(i,1,n)
- {
- if(!dfn[i])
- tarjan(i);
- }
- f(i,1,n)dbg(low[i]);
- if(cnt==1)pf("Yes\n");
- else pf("No\n");
- }
- }
来源: https://www.cnblogs.com/randy-lo/p/12588025.html