[HAOI2006]受欢迎的牛（tarjan缩点）

洛谷传送门

直接tarjan求scc，然后统计出度为0的缩点，如果多余1个就输出0，只有一个就输出这个缩点里的点。

——代码

1 #include <cstdio> 2 #include <cstring> 3 #include <stack> 4 5 using namespace std; 6 7 int n, m, cnt, idx, ans, k; 8 int next[100001], to[100001], head[10001], low[10001], dfn[10001], belong[10001], c[10001]; 9 bool ins[10001]; 10 stack <int> s; 11 12 inline void add(int x, int y) 13 18 19 inline void tarjan(int u) 20 33 else if(ins[v]) low[u] = min(low[u], dfn[v]); 34 } 35 if(low[u] == dfn[u]) 36 while(u != v); 45 } 46 } 47 48 int main() 49 58 cnt = 0; 59 for(i = 1; i <= n; i++) 60 if(!dfn[i]) 61 tarjan(i); 62 for(u = 1; u <= n; u++) for(i = head[u]; i != 1; i = next[i]) 64 68 for(i = 1; i <= cnt; i++) 69 if(!c[i]) 70 74 if(ans > 1) printf("0"); 75 else 76 83 return 0; 84 }
View Code

上一篇：公路修建（Prim）

下一篇：[HDU2222]Keywords Search（AC自动机）

---

tarjan SCC