tarjan
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 |
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 1e4 + 10, M = 5e4 + 10; int n, m; int h[N], e[M], ne[M], idx; int dfn[N], low[N], timestamp; int stk[N], top; bool in_stk[N]; int id[N], scc_cnt, siz[N]; int dout[N]; void add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx ++; } void tarjan(int u) { dfn[u] = low[u] = ++ timestamp; stk[++ top] = u, in_stk[u] = true; 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 y; do { y = stk[top --]; in_stk[y] = false; id[y] = scc_cnt; siz[scc_cnt] ++; } while (y != u); } } int main() { scanf("%d%d", &n, &m); memset(h, -1, sizeof h); while (m --) { int a, b; scanf("%d%d", &a, &b); add(a, b); } for (int i = 1; i <= n; ++ i) if (!dfn[i]) tarjan(i); for (int i = 1; i <= n; ++ i) for (int j = h[i]; ~j; j = ne[j]) { int k = e[j]; int a = id[i], b = id[k]; if (a != b) dout[a] ++; } int zeros = 0, sum = 0; for (int i = 1; i <= scc_cnt; ++ i) if (!dout[i]) { zeros ++; sum += siz[i]; if (zeros > 1) { sum = 0; break; } } printf("%d\n", sum); } |
发表回复