关于板子 可参考 wlxy的博客
[HAOI2006]受欢迎的牛 の 传送门
Description 每一头牛的愿望就是变成一头最受欢迎的牛。现在有N头牛，给你M对整数(A,B)，表示牛A认为牛B受欢迎。 这种关系是具有传递性的，如果A认为B受欢迎，B认为C受欢迎，那么牛A也认为牛C受欢迎。你的任务是求出有多少头牛被所有的牛认为是受欢迎的。
Input 第一行两个数N,M。 接下来M行，每行两个数A,B，意思是A认为B是受欢迎的（给出的信息有可能重复，即有可能出现多个A,B）
Output 一个数，即有多少头牛被所有的牛认为是受欢迎的。
Sample Input 3 3 1 2 2 1 2 3
Sample Output 1
「数据范围」 10%的数据N<=20, M<=50 30%的数据N<=1000,M<=20000 70%的数据N<=5000,M<=50000 100%的数据N<=10000,M<=50000
tarjan强连通分量缩点模板题吧虽然很久很久以前我写了很久很久TAT出度为0的点只有一个才有解
Code
//bzoj1051 #include <cstdio> #include <algorithm> #include <iostream> #include <cmath> #include <cstring> #include <stack> using namespace std; const int N = 10007, M = 50007; int n, m, cnt, scc, tim, ans, head[N], to[M], nxt[M], low[N], dfn[N], belong[N], vis[N], hav[N], chu[N]; stack <int> S; inline int read(){ int ans = 0, f = 1; char ch = getchar(); for(; ch < '0' || ch > '9'; ch = getchar()) if (ch == '-') f = 0; for(; ch >= '0' && ch <= '9'; ch = getchar()) ans = (ans << 3) + (ans << 1) + ch - 48; return f? ans: -ans; } void add(int u, int v){nxt[++cnt] = head[u]; to[cnt] = v; head[u] = cnt;} void tarjan(int u){ dfn[u] = low[u] = ++tim; S.push(u); vis[u] = 1; int v; for (int i = head[u]; i; i = nxt[i]){ v = to[i]; if (!dfn[v]) tarjan(v), low[u] = min(low[u], low[v]); else if (vis[v]) low[u] = min(low[u], dfn[v]); } if (dfn[u] == low[u]){ scc++; do { v = S.top(); vis[v] = 0; belong[v] = scc; hav[scc]++; S.pop(); } while(u != v); } } int main(){ tim = cnt = scc = 0; n = read(), m = read(); while (S.size()) S.pop(); for (register int i = 1; i <= m; ++i){ int u = read(), v = read(); add(u, v); } for (register int i = 1; i <= n; ++i) if (!dfn[i]) tarjan(i); for (register int k = 1; k <= n; ++k) for (int i = head[k]; i; i = nxt[i]){ int v = to[i]; if (belong[k] != belong[v]) chu[belong[k]]++; } ans = 0; for (int i = 1; i <= scc; ++i){ if (!chu[i]) if (ans){ printf("0\n"); return 0; } else ans = hav[i]; } printf("%d\n", ans); return 0; }转载于:https://www.cnblogs.com/DorkyTAT/p/10333695.html
