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
HINT
100%的数据N<=10000,M<=50000
#include<iostream> #include<cstdio> #include<cstring> #include<stack> using namespace std; const int MAXN = 50010; struct Edge { int f, t; }es[MAXN]; int first[MAXN], nxt[MAXN], scc_cnt, sccnum[MAXN], scctong[MAXN], low[MAXN]; stack < int > s; int n, m, pre[MAXN], dfs_clock, cd[MAXN], tot = 1; int ff[MAXN], tt[MAXN]; void build(int f, int t) { es[++tot].t = t; nxt[tot] = first[f]; first[f] = tot; } void dfs(int u) { pre[u] = low[u] = ++dfs_clock; s.push(u); for(int i = first[u]; i ; i = nxt[i]) { int v = es[i].t; if(!pre[v]) { dfs(v); low[u] = min(low[u], low[v]); } else if(!sccnum[v]) { low[u] = min(low[u], pre[v]); } } if(low[u] == pre[u]) { scc_cnt++; for(;;) { int x = s.top(); s.pop(); sccnum[x] = scc_cnt; scctong[scc_cnt]++; if(x == u) break; } } } int main() { scanf("%d%d", &n, &m); for(int i = 1; i <= m; i++) { scanf("%d%d", &ff[i], &tt[i]); build(ff[i], tt[i]); } for(int i = 1; i <= n; i++) if(!pre[i]) dfs(i); for(int i = 1; i <= m; i++) { if(sccnum[ff[i]] != sccnum[tt[i]]) { cd[sccnum[ff[i]]]++; } } int ans = 0, tot = 0; for(int i = 1; i <= scc_cnt; i++) { if(cd[i] == 0) { ans += scctong[i]; tot ++; } } if(tot == 1) printf("%d", ans); else printf("%d", 0); return 0; }转载于:https://www.cnblogs.com/Loi-Vampire/p/6017063.html
