文章目录 强连通分量利用Tarjan算法求强连通分量来一道例题练手(USACO08DEC)图论文章汇总
强连通分量
什么是强连通图?
如果一个有向图中,存在一条回路,所有的结点至少被经过一次,这样的图为强连通图。
什么是强连通分量?
在强连图图的基础上加入一些点和路径,使得当前的图不在强连通,称原来的强连通的部分为强连通分量。
求强连通分量有何作用?
在进行对其它图论问题的求解前,利用强连通分量的知识可以把图中强连通的点缩为一个点,减少接下来其它图论操作的计算。
在某些特定的环境下,求强连通分量变相地得出图中的环以及环的长度。
Tarjan算法的基本思路
首先考虑强连通分量的性质,即存在一条回路能从初始点又回到初始点。在这个查找的过程中,可以对经过的结点标记,当发现某一节点连向的点正好以及被标记过,则说明找到了一条回路,而这个回路上的所有点构成一个强连通分量。为了保存这个强连通分量,我们需要知道这条路上有哪些点,而此时,栈就是一种适合该算法的数据结构。对于每次搜索的点,我们都加入栈中,遇到回路时,在把栈中的元素逐个弹出,记录它们的起始结点,直到栈中弹出的元素正好是起始结点时,结束弹栈,继续搜索其它强连通分量。在这个过程中,所有的点和都有的边都被遍历了一次,所以最终的时间复杂度为 O ( N + E ) O(N+E) O(N+E)
Tarjan算法的实现
为了实现这个过程,Tarjan算法需要装备如下几样东西:
记录搜索顺序的数组 d f n dfn dfn;
记录所属强连通的数组 l o w low low;
表示某结点是否在栈中的数组 i n s t a c k instack instack;
一个栈存储搜索路径;
从上面对Tarjan算法的描述中,很容易看出这个算法是基于深度优先搜索实现的。接下来,对Tarjan算法进行逐步推演。
(本人不喜欢使用网上用烂的素材,接下来包括以前的讲解图都是自己手画的,不喜勿喷)
Tarjan算法伪代码
Tarjan算法C++代码模板
按照先前的推演图,生成测试样例
7 11
1 2
2 3
2 5
2 4
3 5
3 7
7 5
5 6
6 7
4 1
4 5
运行结果与推演时一致
——题目描述——
每年,在威斯康星州,奶牛们都会穿上衣服,收集农夫约翰在N(1<=N<=100,000)个牛棚隔间中留下的糖果,以此来庆祝美国秋天的万圣节。
由于牛棚不太大,FJ通过指定奶牛必须遵循的穿越路线来确保奶牛的乐趣。为了实现这个让奶牛在牛棚里来回穿梭的方案,FJ在第i号隔间上张贴了一个“下一个隔间”Next_i(1<=Next_i<=N),告诉奶牛要去的下一个隔间;这样,为了收集它们的糖果,奶牛就会在牛棚里来回穿梭了。
FJ命令奶牛i应该从i号隔间开始收集糖果。如果一只奶牛回到某一个她已经去过的隔间,她就会停止收集糖果。
在被迫停止收集糖果之前,计算一下每头奶牛要前往的隔间数(包含起点)。
——输入格式——
第1行 整数n。
第2行到n+1行 每行包含一个整数 next_i 。
——输出格式——
n行,第i行包含一个整数,表示第i只奶牛要前往的隔间数。
——输入样例——
4
1
3
2
3
——输出样例——
1
2
2
3
——题解——
本题的数据量还是蛮大的,有 1 e 5 1e5 1e5个结点,我们当然不可能对每一个结点进行深度优先搜索。幸运的是,每一个点都只有一条出边,也即意味着,本题中至少有一个环(包括自环),而且,环上的点永远无法走出这个环,环上点的答案就是这个环的长度。而对于不在环上的点,用dfs直到找到一个环,其答案也即环的长度加上搜索到环的步数。环长度的计算,可以利用tarjan算法的思路,用dfn减去low。因地制宜,我写了一个简易版的tarjan.
——Code——
#include<iostream>#include<stack>#include<algorithm>using namespace std;int edge[100005];int dfn[100005];bool vis[100005];int ans[100005];stack<int> sta;int n;int cnt_dfn;void dfs(int u){++cnt_dfn;dfn[u]=cnt_dfn;vis[u]=true;sta.push(u);if(vis[edge[u]]){if(!ans[edge[u]]){int val=dfn[u]-dfn[edge[u]]+1;int v;do{v=sta.top();ans[v]=val;sta.pop();}while(v!=edge[u]);while(!sta.empty()){++val;ans[sta.top()]=val;sta.pop();}}else{int val=ans[edge[u]];while(!sta.empty()){++val;ans[sta.top()]=val;sta.pop();}}}else dfs(edge[u]);}int main(){cin>>n;for(int i=1;i<=n;++i){cin>>edge[i];if(edge[i]==i){ans[i]=1;vis[i]=true;}}for(int i=1;i<=n;++i)if(!vis[i]){cnt_dfn=0; dfs(i);}for(int i=1;i<=n;++i)cout<<ans[i]<<endl;return 0;} 图论文章汇总图论简笔(上)——DFS、BFS、Toplogical Sort
图论简笔(下)——最小生成树、最短路径问题
图论——强连通分量(Tarjan算法)
图论——最大流的增广路相关算法(基于Ford–Fulkerson方法的DFS和BFS、Dinic算法)
图论——涵盖Bellman-Ford和Dijkstra的Johnson算法(多源最短路径问题)
图论——最大团问题和最大独立集、二分图相关