大意：牛牛之间互相喜欢，而且这种喜欢具有传递性，要求你求出最受欢迎的牛牛们的个数（A single integer that is the number of cows who are considered popular by every other cow. ）
思路：通过“缩点”之后，然后求强连通分量出度的个数，如果为一，那么求出这个“缩点”里所有牛牛的个数。如果大于一，没有符合条件的，手推一遍即可证实。
CODE：
#include <iostream> #include <cstring> #include <cstdio> #include <cstdlib> using namespace std; #define MAXN 10010 #define MAXM 100010 struct Edge { int v, w, next; }edge[MAXM]; int first[MAXN], stack[MAXN], ins[MAXN], dfn[MAXN], low[MAXN]; int belong[MAXM]; int outd[MAXN]; int n, m; int cnt; int scnt, top, tot; void init() { cnt = 0; scnt = top = tot = 0; memset(first, - 1, sizeof(first)); memset(dfn, 0, sizeof(dfn)); } void read_graph( int u, int v) { edge[cnt].v = v; edge[cnt].next = first[u]; first[u] = cnt++; } void dfs( int u) { int t; low[u] = dfn[u] = ++tot; ins[u] = 1; stack[top++] = u; for( int e = first[u]; e != - 1; e = edge[e].next) { int v = edge[e].v; if(!dfn[v]) { dfs(v); low[u] = min(low[u], low[v]); } else if(ins[v]) { low[u] = min(low[u], dfn[v]); } } if(low[u] == dfn[u]) { ++scnt; do { t = stack[--top]; belong[t] = scnt; ins[t] = 0; } while(t != u); } } void Tarjan() { for( int v = 1; v <= n; v++) if(!dfn[v]) dfs(v); } void solve() { Tarjan(); // Tarjan(); memset(outd, 0, sizeof(outd)); for( int u = 1; u <= n; u++) { for( int e = first[u]; e != - 1; e = edge[e].next) { int v = edge[e].v; if(belong[u] != belong[v]) outd[belong[u]]++; // 强连通分量的出度增加，即缩点的出度增加。 } } int index = 0, flag = 0; for( int i = 1; i <= scnt; i++) if(!outd[i]) // 如果强连通的出度为0 { index++; flag = i; // 标记所在强连通 } if(index > 1) printf( " 0\n "); // 出度为0的强连通不只一个 else { index = 0; for( int i = 1; i <= n; i++) if(belong[i] == flag) index++; // 所有的顶点属于出度为0的强连通分量点的数目 printf( " %d\n ", index); } } int main() { while(~scanf( " %d%d ", &n, &m)) { init(); while(m--) { int u, v; scanf( " %d%d ", &u, &v); read_graph(u, v); } solve(); } return 0; }