传送门
有向图，找点数大于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
上一篇：考后总结
下一篇：[BZOJ3196] [Tyvj1730] 二逼平衡树（线段树 套 Splay）
tarjan SCC
