[luoguP2863] [USACO06JAN]牛的舞会The Cow Prom（Tarjan）

传送门

有向图，找点数大于1的强连通分量个数

——代码

1 #include <stack> 2 #include <cstdio> 3 #include <cstring> 4 #include <iostream> 5 6 const int MAXN = 50001; 7 int n, m, cnt, idx, size, ans; 8 int head[MAXN], to[MAXN << 1], next[MAXN << 1]; 9 int dfn[MAXN], low[MAXN], belong[MAXN], tot[MAXN]; 10 bool ins[MAXN]; 11 std::stack <int> s; 12 13 inline int read() 14 21 22 inline int min(int x, int y) 23 26 27 inline void add(int x, int y) 28 33 34 inline void dfs(int u) 35 48 else if(ins[v]) low[u] = min(low[u], dfn[v]); 49 } 50 if(low[u] == dfn[u]) 51 60 while(u ^ v); 61 } 62 } 64 int main() 65 76 for(i = 1; i <= n; i++) 77 if(!dfn[i]) 78 dfs(i); 79 for(i = 1; i <= n; i++) tot[belong[i]]++; 80 for(i = 1; i <= size; i++) 81 if(tot[i] > 1) 82 ans++; 83 printf("%d\n", ans); 84 return 0; 85 }
View Code

上一篇：[luoguP2434] [SDOI2005]区间（贪心）

下一篇：[luoguP2854] [USACO06DEC]牛的过山车Cow Roller Coaster（DP + sort）

---

tarjan SCC