传送门

有向图，找点数大于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