【题目来源】
洛谷：P2863 [USACO06JAN] The Cow Prom S - 洛谷
【题目描述】
有一个 \(n\) 个点，\(m\) 条边的有向图，请求出这个图点数大于 \(1\) 的强连通分量个数。
【输入】
第一行为两个整数 \(n\) 和 \(m\)。
第二行至 \(m+1\) 行，每一行有两个整数 \(a\) 和 \(b\)，表示有一条从 \(a\) 到 \(b\) 的有向边。
【输出】
仅一行，表示点数大于 \(1\) 的强连通分量个数。
【输入样例】
5 4
2 4
3 5
1 2
4 1
【输出样例】
1
【算法标签】
《洛谷 P2863 The Cow Prom》 #强连通分量# #Tarjan# #USACO# #2006#
【代码详解】
#include <bits/stdc++.h>
using namespace std;const int N = 1e4 + 5; // 定义最大节点数// 全局变量声明
int n, m; // n: 节点数，m: 边数
vector<int> e[N]; // 图的邻接表
int dfn[N], low[N]; // dfn: 访问时间戳，low: 最早可回溯到的节点时间戳
int tot; // 时间戳计数器
int stk[N], instk[N]; // stk: 栈，instk: 标记节点是否在栈中
int top; // 栈顶指针
int scc[N], siz[N]; // scc: 节点所属SCC编号，siz: 每个SCC的大小
int cnt; // SCC计数器/*** Tarjan算法求强连通分量* @param x 当前访问的节点*/
void tarjan(int x)
{// 入栈处理：设置时间戳并入栈dfn[x] = low[x] = ++tot;stk[++top] = x;instk[x] = 1;// 遍历所有邻接节点for (int y : e[x]){if (!dfn[y]) // 如果y未被访问过{tarjan(y);low[x] = min(low[x], low[y]); // 回溯时更新low值}else if (instk[y]) // 如果y在栈中{low[x] = min(low[x], dfn[y]); // 更新low值}}// 判断是否为SCC根节点if (dfn[x] == low[x]){int y;++cnt; // 增加SCC计数do{y = stk[top--]; // 弹出栈顶元素instk[y] = 0; // 标记为不在栈中scc[y] = cnt; // 记录SCC编号++siz[cnt]; // 增加当前SCC的大小} while (y != x); // 直到处理完当前SCC的所有节点}
}int main()
{// 输入节点数和边数cin >> n >> m;// 构建图的邻接表for (int i = 1; i <= m; i++){int a, b;cin >> a >> b;e[a].push_back(b);}// 对每个未访问的节点执行Tarjan算法for (int i = 1; i <= n; i++){if (!dfn[i]){tarjan(i);}}// 统计大小大于1的SCC数量int ans = 0;for (int i = 1; i <= cnt; i++){if (siz[i] > 1){ans++;}}// 输出结果cout << ans << endl;return 0;
}
【运行结果】
5 4
2 4
3 5
1 2
4 1
1