《P2863 [USACO06JAN] The Cow Prom S》

题目描述

有一个 n 个点，m 条边的有向图，请求出这个图点数大于 1 的强连通分量个数。

输入格式

第一行为两个整数 n 和 m。

第二行至 m+1 行，每一行有两个整数 a 和 b，表示有一条从 a 到 b 的有向边。

输出格式

仅一行，表示点数大于 1 的强连通分量个数。

输入输出样例

输入 #1复制

5 4
2 4
3 5
1 2
4 1

输出 #1复制

1

说明/提示

数据规模与约定

对于全部的测试点，保证 2≤n≤104，2≤m≤5×104，1≤a,b≤n。

代码实现：

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

const int MAXN = 10010; // 最大节点数

vector<int> adj[MAXN]; // 邻接表存储图
int index = 0; // 时间戳
int indices[MAXN]; // 每个节点的发现时间
int low[MAXN]; // 每个节点能访问到的最早发现时间的节点
bool onStack[MAXN]; // 标记节点是否在栈中
stack<int> stk; // 存储当前路径上的节点
int sccCount = 0; // 节点数大于1的强连通分量个数

// Tarjan算法的核心递归函数
void tarjan(int u) {
indices[u] = low[u] = ++index; // 初始化发现时间和最早可达时间
stk.push(u); // 将节点入栈
onStack[u] = true; // 标记节点在栈中

// 遍历所有邻接节点（使用传统for循环代替范围for循环）
for (int i = 0; i < adj[u].size(); i++) {
int v = adj[u][i]; // 获取邻接节点
if (indices[v] == 0) { // 如果邻接节点未被访问
tarjan(v); // 递归访问
low[u] = min(low[u], low[v]); // 更新当前节点的最早可达时间
} else if (onStack[v]) { // 如果邻接节点在当前栈中（即属于当前SCC）
low[u] = min(low[u], indices[v]); // 更新当前节点的最早可达时间
}
}

// 如果当前节点是一个SCC的根节点
if (low[u] == indices[u]) {
int count = 0; // 当前SCC的节点数
int v;
do {
v = stk.top();
stk.pop();
onStack[v] = false;
count++;
} while (v != u);

// 如果SCC的节点数大于1，则计数加1
if (count > 1) {
sccCount++;
}
}
}

int main() {
int n, m;
cin >> n >> m;

// 初始化数据结构
for (int i = 1; i <= n; i++) {
adj[i].clear();
indices[i] = 0;
low[i] = 0;
onStack[i] = false;
}

// 读取边（使用传统for循环）
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
adj[a].push_back(b);
}

// 对每个未访问的节点调用Tarjan算法（使用传统for循环）
for (int i = 1; i <= n; i++) {
if (indices[i] == 0) {
tarjan(i);
}
}

// 输出结果
cout << sccCount << endl;

return 0;
}