【题目来源】
洛谷：P2341 [USACO03FALL / HAOI2006] 受欢迎的牛 G - 洛谷
【题目描述】
每头奶牛都梦想成为牛棚里的明星。被所有奶牛喜欢的奶牛就是一头明星奶牛。所有奶牛都是自恋狂，每头奶牛总是喜欢自己的。奶牛之间的“喜欢”是可以传递的——如果 \(A\) 喜欢 \(B\)，\(B\) 喜欢 \(C\)，那么 \(A\) 也喜欢 \(C\)。牛栏里共有 \(N\) 头奶牛，给定一些奶牛之间的爱慕关系，请你算出有多少头奶牛可以当明星。
【输入】
第一行：两个用空格分开的整数：\(N\) 和 \(M\)。
接下来 \(M\) 行：每行两个用空格分开的整数：\(A\) 和 \(B\)，表示 \(A\) 喜欢 \(B\)。
【输出】
一行单独一个整数，表示明星奶牛的数量。
【输入样例】
3 3
1 2
2 1
2 3
【输出样例】
1
【算法标签】
《洛谷 P2341 受欢迎的牛》 #图论# #强连通分量# #Tarjan# #栈# #USACO# #各省省选# #2003# #2006# #河南#
【代码详解】
#include <bits/stdc++.h>
using namespace std;const int N = 10005; // 最大节点数int n, m, a, b; // n:节点数, m:边数, a,b:临时边变量
vector<int> e[N]; // 邻接表存储图int dfn[N]; // DFS序（时间戳）
int low[N]; // 通过回边能到达的最小DFN值
int tot; // 时间戳计数器int stk[N]; // Tarjan算法栈
int instk[N]; // 标记节点是否在栈中
int top; // 栈顶指针int scc[N]; // 存储每个节点所属的强连通分量编号
int siz[N]; // 存储每个强连通分量的大小（节点数）
int cnt; // 强连通分量计数器int dout[N]; // 每个强连通分量的出度/*** Tarjan算法求强连通分量* @param x 当前节点*/
void tarjan(int x)
{// 初始化当前节点的DFN和LOW值dfn[x] = low[x] = ++tot;// 将当前节点压入栈并标记stk[++top] = x;instk[x] = 1;// 遍历当前节点的所有邻接节点for (int y : e[x]){// 如果邻接节点y未被访问if (!dfn[y]){tarjan(y); // 递归访问ylow[x] = min(low[x], low[y]); // 更新low值}// 如果y已被访问且在栈中（回边）else if (instk[y]){low[x] = min(low[x], dfn[y]); // 通过回边更新low值}}// 如果当前节点是强连通分量的根if (dfn[x] == low[x]){int y;++cnt; // 增加强连通分量计数// 弹出栈中节点直到遇到当前节点do{y = stk[top--]; // 弹出栈顶节点instk[y] = 0; // 标记节点已出栈scc[y] = cnt; // 记录节点所属的强连通分量++siz[cnt]; // 增加当前强连通分量的大小}while (y != x); // 直到弹出当前节点}
}int main()
{// 输入节点数和边数cin >> n >> m;// 输入所有边while (m--){cin >> a >> b;e[a].push_back(b); // 添加有向边a->b}// 对每个未访问的节点执行Tarjan算法for (int i = 1; i <= n; i++){if (!dfn[i]){tarjan(i);}}// 构建强连通分量之间的有向无环图（DAG）for (int x = 1; x <= n; x++){for (int y : e[x]){// 如果x和y不在同一个强连通分量中if (scc[x] != scc[y]){++dout[scc[x]]; // 源分量的出度增加}}}// 统计出度为0的强连通分量int sum = 0; // 存储最终结果int zeros = 0; // 出度为0的强连通分量数量for (int i = 1; i <= cnt; i++){// 如果当前强连通分量出度为0if (dout[i] == 0){sum = siz[i]; // 记录该分量的大小++zeros; // 增加出度为0的分量计数}}// 如果有多个出度为0的强连通分量，则结果为0if (zeros > 1){sum = 0;}// 输出结果cout << sum << endl;return 0;
}
【运行结果】
3 3
1 2
2 1
2 3
1