/*
* @Author: thyzzs
* @Date: 2019-08-02 16:55:56
* @LastEditTime: 2019-11-14 09:44:57
*/
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#define MAX_N 1000005
using namespace std;
//定理:一个SCC从其中任何一个点出发,都至少有一条路径能绕回自己
int cnt; // 强连通分量个数
int low[MAX_N], num[MAX_N], dfn; // num[]代表dfs对每个点的访问顺序,low[]代表能返回到的最远祖先的num值
// 相同low值代表一个SCC,初始low值等于num
// dfn代表进入递归的顺序,用于给num赋值(时间戳)
int scc[MAX_N], stack[MAX_N], top; // stack[]模拟栈,top是栈顶
vector<int> G[MAX_N];
inline void dfs(int u) {
stack[top++] = u; // u进栈
low[u] = num[u] = ++dfn;
for (register int i = 0; i < G[u].size(); i++) {
int v = G[u][i];
if (!num[v]) { // 未访问过的点,继续dfs
dfs(v);
low[u] = min(low[v], low[u]);
} else if (!scc[v]) // 处理回退边
low[u] = min(low[u], num[v]);
}
if (low[u] == num[u]) { // 栈底的点是SCC的祖先,它的low = num
cnt++;
while (1) {
int v = stack[--top]; // v弹出栈
scc[v] = cnt;
if (u == v) break; // 栈底的点是SCC的祖先
}
}
}
inline void Tarjan(int n) {
cnt = top = dfn = 0;
memset(scc, 0, sizeof(scc));
memset(num, 0, sizeof(num));
memset(low, 0, sizeof(low));
for (register int i = 1; i <= n; i++)
if (!num[i]) dfs(i);
}
int main() {
int n, m, u, v;
scanf("%d%d", &n, &m);
for (register int i = 0; i < m; i++) {
scanf("%d%d", &u, &v);
G[u].push_back(v);
}
Tarjan(n);
return 0;
}
Publish Date:
2019-11-14
Word Count:
356
Read Times:
1 Min
All articles in this blog are used except for special statements
CC BY-NC-SA 4.0
reprint policy. If reproduced, please indicate source
thyzzs
!
评论