许诺 • 18天前
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAXN = 205;
vector graph[MAXN], reverseGraph[MAXN]; bool visited[MAXN]; stack finishOrder; int component[MAXN]; int inDegree[MAXN];
void dfs1(int u) {
visited[u] = true;
for (int v : graph[u]) {
if (!visited[v]) {
dfs1(v);
}
}
finishOrder.push(u);
}
void dfs2(int u, int compId) {
visited[u] = true;
component[u] = compId;
for (int v : reverseGraph[u]) {
if (!visited[v]) {
dfs2(v, compId);
}
}
}
int main() {
int n;
cin >> n;
// 构建图和反向图
for (int i = 1; i <= n; i++) {
int x;
while (cin >> x && x != 0) {
graph[i].push_back(x);
reverseGraph[x].push_back(i);
}
}
// 第一次DFS,确定完成顺序
memset(visited, false, sizeof(visited));
for (int i = 1; i <= n; i++) {
if (!visited[i]) {
dfs1(i);
}
}
// 第二次DFS,在反向图上找强连通分量
memset(visited, false, sizeof(visited));
int compCount = 0;
while (!finishOrder.empty()) {
int u = finishOrder.top();
finishOrder.pop();
if (!visited[u]) {
compCount++;
dfs2(u, compCount);
}
}
// 计算每个强连通分量的入度
memset(inDegree, 0, sizeof(inDegree));
for (int u = 1; u <= n; u++) {
for (int v : graph[u]) {
if (component[u] != component[v]) {
inDegree[component[v]]++;
}
}
}
// 统计入度为0的强连通分量数量
int result = 0;
for (int i = 1; i <= compCount; i++) {
if (inDegree[i] == 0) {
result++;
}
}
cout << result << endl;
return 0;
}
评论:
请先登录,才能进行评论