算法学习：强连通分量 --tarjan

【定义】

【强连通分量】

 在一个子图中，任意点能够直接或者间接到达这个子图中的任意点，这个子图被称为强连通分量

 

---

【解决问题】

求图的强连通分量

同时能够起到

...................缩点

...................求割点

...................求割边

的效果

 

---

【算法学习】

首先明确我们的目的，找到强联通分量

所以其实这是一个找环的过程

 

dfn [] :表示 dfs 序

low [] :表示强联通分量里面 dfs 序最小的 dfs 序

 

方法如下：

 按深度优先遍历所有节点

 

遍历当前节点的所有出边

 

　　1.如果当前边的中点还没有被访问过，访问

　　回溯回来之后比较当前节点的 low 值和终点的 low 值

　　将较小的变为当前节点的 low 值

 

　　2.如果访问过，则说明我们绕了一个圈

　　则比较当前节点的low值和终点的dfn值，将较小的作为当前结点的low值

 

当这个节点的dfn值和low值相等的时候，说明这个点是这个强联通分量的终点

在这个栈上面的点和这个点都在同一个强联通分量里面

 

伪代码如下：

void tarjan(int u) //当前节点 {dfn[u]=low[u]=++cnt;//先默认该点是一个强联通分量//节点入栈;vis[u]=true;//当前节点已入栈for(遍历该节点所有出边){int v=当前边的终点;if (!dfn[v])//如果没有被遍历过 {tarjan(v);//深度优先遍历low[u]=min(low[u],low[v]);}else low[u]=min(dfn[v],low[u]);}if (low[u]==dfn[u]){//如果找到了最低的那个节点while(栈顶!=v){染色;出栈;}}染色;出栈; }

 

---

【模板】

【luogu 2863】

【题目大意】求图内强联通分量内点个数大于1的强连通分量个数

【题目思路】裸的tarjan求强连通分量

 

再次强调下

分清边的数量和点的数量

分清双向边和单向边

 

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<queue> #include<stack> using namespace std; const int MAXN = 50010; struct note {int nt;int to; }edge[MAXN]; int top = 0,st[MAXN]; int cnt[MAXN]; int tag[MAXN]; int n, m; void add(int x, int y) {top++; edge[top] = { st[x],y }, st[x] = top; } stack<int> s; int dfn[MAXN], low[MAXN],id,col; bool vis[MAXN]; void tarjan(int now) {dfn[now] = low[now] = ++id;vis[now] = true;s.push(now);for (int i = st[now]; i != -1; i = edge[i].nt){int to = edge[i].to;if (!dfn[to]){tarjan(to);low[now] = min(low[now], low[to]);}else{if (vis[to]){low[now] = min(low[now], dfn[to]);}}}if (dfn[now] == low[now]){col++; int t;do {t = s.top();s.pop();tag[t] = col;cnt[col]++;vis[t] = false;} while (t != now);}} int main() {scanf("%d%d", &n, &m);memset(st, -1, sizeof(st));for (int i = 1; i <= m; i++){int x, y;scanf("%d%d", &x, &y);add(x, y);}int ans = 0;for (int i = 1; i <= n; i++){if (!tag[i])tarjan(i);}for (int i = 1; i <= col; i++)if (cnt[i] > 1)ans++;printf("%d", ans);return 0; } View Code

 

---

 

【扩展】

求割点

 

求割边

 

 

---

 

转载于:https://www.cnblogs.com/rentu/p/11331123.html

总结

以上是生活随笔为你收集整理的算法学习：强连通分量 --tarjan的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。