[USACO03FALL / HAOI2006] 受欢迎的牛 G（C++，强连通分量）

题目背景

本题测试数据已修复。

题目描述

每头奶牛都梦想成为牛棚里的明星。被所有奶牛喜欢的奶牛就是一头明星奶牛。所有奶牛都是自恋狂，每头奶牛总是喜欢自己的。奶牛之间的“喜欢”是可以传递的——如果 $A$ 喜欢 $B$，$B$ 喜欢 $C$，那么 $A$ 也喜欢 $C$。牛栏里共有 $N$ 头奶牛，给定一些奶牛之间的爱慕关系，请你算出有多少头奶牛可以当明星。

输入格式

第一行：两个用空格分开的整数：$N$ 和 $M$。

接下来 $M$ 行：每行两个用空格分开的整数：$A$ 和 $B$，表示 $A$ 喜欢 $B$。

输出格式

一行单独一个整数，表示明星奶牛的数量。

样例 #1

样例输入 #1

3 3
1 2
2 1
2 3

样例输出 #1

1

提示

只有 $3$ 号奶牛可以做明星。

【数据范围】

对于 $10\%$ 的数据，$N\le 20$，$M\le 50$。

对于 $30\%$ 的数据，$N\le 10^3$，$M\le 2\times 10^4$。

对于 $70\%$ 的数据，$N\le 5\times 10^3$，$M\le 5\times 10^4$。

对于 $100\%$ 的数据，$1\le N\le 10^4$，$1\le M\le 5\times 10^4$。

解题思路：

根据题意中的“喜欢可以传递”，在一个爱慕环中的奶牛可以缩成一头奶牛

因为环中任何一头奶牛所喜欢的也被环中其他的奶牛喜欢

喜欢环中任何一头奶牛也会喜欢环中所有的奶牛

采用tarjan缩点，生成一张新图，图中的所有奶牛都是“单相思”

只有图中出度为$0$的节点可能是明星奶牛

因为“单相思”不会得到回应，也就不会符合“被所有奶牛喜欢”这一条件

但是如果有多个出度为$0$的节点，那么就不存在明星奶牛，因为出度为$0$的奶牛不会互相喜欢

AC代码如下

#include <iostream>
#include <string.h>
#include <queue>
using namespace std;
const int max_n = 1e4;
const int max_m = 5e4;int n, m, u, v;
//链式前向星
int head[max_n + 1];
int tot = -1;
struct edge { int v, next; }edges[max_m];
//tarjan缩点
int timeclock = 0, dfn[max_n + 1], low[max_n + 1];
int in_stack[max_n + 1], stack[max_n], rsp = -1;
//新图
int belong[max_n + 1], power[max_n + 1], cnt = 0;
int out[max_n + 1];//入度void add_edge(int u, int v) {edges[++tot] = { v, head[u] }; head[u] = tot;
}void tarjan(int s) {dfn[s] = low[s] = ++timeclock;stack[++rsp] = s;in_stack[s] = 1;for (int i = head[s]; i != -1; i = edges[i].next) {int v = edges[i].v;if (!dfn[v]) {tarjan(v);low[s] = min(low[s], low[v]);}else if (in_stack[v]) {low[s] = min(low[s], low[v]);}}if (dfn[s] == low[s]) {cnt++;while (stack[rsp + 1] != s) {belong[stack[rsp]] = cnt;power[cnt]++;//记录合并节点的数量in_stack[stack[rsp]] = 0;rsp--;}}
}int main() {memset(head + 1, -1, sizeof(int) * max_n);cin >> n >> m;for (int i = 0; i < m; i++) {cin >> u >> v;add_edge(u, v);}for (int i = 1; i <= n; i++) {if (!dfn[i]) {tarjan(i);}}for (int i = 1; i <= n; i++) {for (int j = head[i]; j != -1; j = edges[j].next) {int v = edges[j].v;//出度计数if (belong[i] != belong[v]) {out[belong[i]]++;}}}int ans = 0, find = 0;for (int i = 1; i <= cnt; i++) {if (!out[i]) {if (find) {cout << 0 << endl;return 0;}else {find++;ans = i;}}}cout << power[ans] << endl;return 0;
}