AC

许诺  •  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;

}


评论:

请先登录,才能进行评论