因为仰慕关系具有传递性，因此在一个强连通分量中，每个奶牛都被分量中的其他奶牛膜拜，而且也膜拜着分量中的其他奶牛，这种互相膜拜的场景在现实生活中也是经常存在的，因此，本题可以将强连通分量缩点，并构造新图，最后做一次扫描，统计出度为0的点的个数，如果正好为1，表示这个强连通分量（可能是一个点，也可能是多个点）中的奶牛都符合条件，输出其中的个数即可。 如果不唯一，显然就没有奶牛符合被所有奶牛膜拜的条件了。
#include<iostream> #include<vector> #include<cstring> #include<queue> #define INF 99999999 using namespace std; int n, m; int num[10005];//第i个强连通分量包含的个数 bool P[10005];//DFS判重 int flag[10005];//该点是属于第几个强连通分量 vector<int> v[10005];//正向图 vector<int> rv[10005];//反向图 vector<int> s; int cnt; void dfs1(int x){ P[x] = 1; for (int i = 0; i < v[x].size(); i++) if (!P[v[x][i]]) dfs1(v[x][i]); s.push_back(x); } void dfs2(int x){ flag[x] = cnt; num[cnt]++; P[x] = 1; for (int i = 0; i < rv[x].size(); i++) if (!P[rv[x][i]]) dfs2(rv[x][i]); } void Kosaraju(){ memset(P, 0, sizeof(P)); for (int i = 1; i <= n; i++) { for (int j = 0; j < v[i].size(); j++){//检查强连通分量是否有出度,有就对应的P[i]=1 int w = v[i][j]; if (flag[i] != flag[w]) P[flag[i]] = 1;//这个强连通分量标记为1 } } int ans; int t = 0; for (int i = 1; i <= cnt; i++){//检查有几个强连通分量的出度为0 if (!P[i]){ ans = i; t++; } } if (t == 1)//如果只有一个强连通分量的入度为0,则输出应的tree_n[i]为要的答案,否则没有 printf("%d\n", num[ans]); else printf("0\n"); } int main(){ int a, b; scanf("%d%d", &n, &m); for (int i = 0; i < m; i++){ scanf("%d%d", &a, &b); v[a].push_back(b); rv[b].push_back(a); } for (int i = 1; i <= n; i++) if (!P[i]) dfs1(i); memset(P, 0, sizeof(P)); memset(num, 0, sizeof(num)); cnt = 0; for (int i = s.size() - 1; i >= 0; i--){ if (!P[s[i]]){ cnt++; dfs2(s[i]); } } Kosaraju(); return 0; }