Acwing 1174. 受欢迎的牛
题意
每一头牛的愿望就是变成一头最受欢迎的牛。
现在有 N头牛，编号从 1 到 N ，给你 M 对整数(A,B) ，表示牛 A认为牛B 受欢迎。 这种关系是具有传递性的，如果A 认为 B 受欢迎，B 认为 C 受欢迎，那么牛 A 也认为牛C 受欢迎。 你的任务是求出有多少头牛被除自己之外的所有牛认为是受欢迎的。
思路
先用tarjan算法求出强连通分量并缩点，缩点后构成一个有向无环图(DAG)，如果这个有向无环图的终点 – 即出度为 0 的点只有一个，则这个点是被所有牛认为是受欢迎的，输出这个强连通分量的大小即可，否则不存在受所有牛欢迎的牛
代码
const int N = 5e4 + 10, M = 5 * N; int n, m; int h[N], e[M], ne[M], idx; int dfn[N], low[N]; int dout[N]; int scc, timestamp; bool in_stk[N]; stack<int>stk; int id[N], siz[N]; void add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx++; } void tarjan(int u) { dfn[u] = low[u] = ++timestamp; stk.push(u), in_stk[u] = true; for (int i = h[u]; ~i; i = ne[i]) { int j = e[i]; if (!dfn[j]) { tarjan(j); low[u] = min(low[u], low[j]); } else if (in_stk[j]) { low[u] = min(low[u], dfn[j]); } } if (dfn[u] == low[u]) { int y = 0; ++scc; do { y = stk.top(); stk.pop(); in_stk[y] = false; id[y] = scc; siz[scc]++; } while (y != u); } } void solve() { scanf("%d%d", &n, &m); memset(h, -1, sizeof h); while (m--) { int u, v; scanf("%d%d", &u, &v); add(u, v); } for (int i = 1; i <= n; ++i) { if (!dfn[i]) tarjan(i); } int cnt = 0; int res = 0; for (int i = 1; i <= n; ++i) { for (int j = h[i]; ~j; j = ne[j]) { int k = e[j]; if (id[i] != id[k]) { dout[id[i]]++; } } } for (int i = 1; i <= scc; ++i) { if (!dout[i])cnt++, res = siz[i]; } if (cnt == 1) cout << res << endl; else puts("0"); } signed main() { //int _; cin >> _; //while (_--) solve(); return 0; }
