You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
67 lines
2.0 KiB
67 lines
2.0 KiB
#include <bits/stdc++.h>
|
|
using namespace std;
|
|
|
|
const int N = 50002, M = N << 1;
|
|
int n, m, ans;
|
|
|
|
int stk[N], top; // tarjan算法需要用到的堆栈
|
|
bool in_stk[N]; // 是否在栈内
|
|
int dfn[N]; // dfs遍历到u的时间
|
|
int low[N]; // 从u开始走所能遍历到的最小时间戳
|
|
int ts; // 时间戳,dfs序的标识,记录谁先谁后
|
|
int id[N], scc_cnt; // 强连通分量块的最新索引号
|
|
int sz[N]; // sz[i]表示编号为i的强连通分量中原来点的个数
|
|
|
|
//链式前向星
|
|
int e[M], h[N], idx, w[M], ne[M];
|
|
void add(int a, int b, int c = 0) {
|
|
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
|
|
}
|
|
|
|
// tarjan算法求强连通分量
|
|
void tarjan(int u) {
|
|
dfn[u] = low[u] = ++ts;
|
|
stk[++top] = u;
|
|
in_stk[u] = 1;
|
|
for (int i = h[u]; ~i; i = ne[i]) {
|
|
int j = e[i];
|
|
if (!dfn[j]) {
|
|
tarjan(j);
|
|
low[u] = min(low[u], low[j]);
|
|
} else if (in_stk[j])
|
|
low[u] = min(low[u], dfn[j]);
|
|
}
|
|
|
|
if (dfn[u] == low[u]) {
|
|
++scc_cnt; // 强连通分量的序号
|
|
int x; // 临时变量x,用于枚举栈中当前强连通分量中每个节点
|
|
|
|
do {
|
|
x = stk[top--]; //弹出节点
|
|
in_stk[x] = false; //标识不在栈中了
|
|
id[x] = scc_cnt; //记录每个节点在哪个强连通分量中
|
|
sz[scc_cnt]++; //这个强连通分量中节点的个数+1
|
|
} while (x != u);
|
|
}
|
|
}
|
|
|
|
int main() {
|
|
memset(h, -1, sizeof h);
|
|
scanf("%d %d", &n, &m);
|
|
|
|
for (int i = 1; i <= m; i++) {
|
|
int a, b;
|
|
scanf("%d %d", &a, &b);
|
|
add(a, b);
|
|
}
|
|
|
|
for (int i = 1; i <= n; i++)
|
|
if (!dfn[i]) tarjan(i);
|
|
|
|
//枚举结果数组，统计题目要求的 点数大于 1 的强联通分量个数
|
|
for (int i = 1; i <= scc_cnt; i++)
|
|
if (sz[i] > 1) ans++;
|
|
|
|
printf("%d\n", ans);
|
|
return 0;
|
|
} |