题意
A -> B表示 A 认为 B是红人，且如果 B -> C，则 A -> C。问有几头牛被所有牛都认为是红人。
分析
如果A被所有牛认为是红人，那么A所在的强连通分量里的牛也被所有牛认为是红人。
至多只有一个强连通分量满足满足题目的条件。（否则这两个强连通分量合并，仍然是一个强连通分量） 按照Kosaraju算法 求强连通分量时，能够得到各个强连通分量拓扑排序后的顺序，而唯一能成为解的只有拓扑排序最后的连通分量， （如果存在这样的强连通分量，那么一定会在第一个DFS中就找到（所有牛都认为它是红人），而由于rDFS逆序遍历，所以编号最大的就是那个强连通分量了。）code
#include#include #include #include #include #include using namespace std;const int MAXN = 1e4 + 10;int n, m; // 点、边int vis[MAXN];int flag[MAXN]; // 所属强连通分量的拓扑序vector G[MAXN], rG[MAXN];vector vs; // 后序遍历顺序的顶点列表void addedge(int x, int y){ G[x].push_back(y); // 正向图 rG[y].push_back(x); // 反向图}void dfs(int u){ vis[u] = 1; for(int i = 0; i < G[u].size(); i++) { int v = G[u][i]; if(!vis[v]) dfs(v); } vs.push_back(u);}void rdfs(int u, int k){ vis[u] = 1; flag[u] = k; for(int i = 0; i < rG[u].size(); i++) { int v = rG[u][i]; if(!vis[v]) rdfs(v, k); }}int scc() // 强连通分量的个数{ vs.clear(); memset(vis, 0, sizeof vis); for(int i = 1; i <= n; i++) // [1...n] if(!vis[i]) dfs(i); memset(vis, 0, sizeof vis); int k = 0; for(int i = vs.size() - 1; i >= 0; i--) if(!vis[vs[i]]) rdfs(vs[i], k++); return k;}int solve(){ int cnt = scc(), num = 0, u = 0; for(int i = 1; i <= n; i++) if(flag[i] == cnt - 1) { num++; u = i; } memset(vis, 0, sizeof vis); rdfs(u, 0); for(int i = 1; i <= n; i++) if(!vis[i]) num = 0; return num;}int main(){ while(~scanf("%d%d", &n, &m)) { for(int i = 0; i <= n; i++) { G[i].clear(); rG[i].clear(); } for(int i = 0; i < m; i++) { int x, y; scanf("%d%d", &x, &y); addedge(x, y); } printf("%d\n", solve()); } return 0;}