用C++编写一段程序,实现以下功能:输出一个有向图中的强连通分量
时间: 2023-12-10 16:42:11 浏览: 85
以下是使用 C++ 实现输出有向图中强连通分量的示例代码:
```cpp
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
// 定义常量,表示最大节点数
const int MAXN = 100;
// 定义邻接表结构体
struct EdgeNode {
int to;
int next;
};
// 定义邻接表数组和 head 数组
EdgeNode edges[MAXN];
int head[MAXN];
int edgeCount = 0;
// 定义 dfs_num 数组和 dfs_low 数组
int dfs_num[MAXN];
int dfs_low[MAXN];
int dfs_count = 0;
// 定义 visited 数组和 scc 数组
bool visited[MAXN];
int scc[MAXN];
int scc_count = 0;
// 定义栈
stack<int> s;
// 添加边的函数
void addEdge(int from, int to) {
edges[++edgeCount].to = to;
edges[edgeCount].next = head[from];
head[from] = edgeCount;
}
// dfs 函数
void dfs(int u) {
dfs_num[u] = dfs_low[u] = ++dfs_count;
s.push(u);
visited[u] = true;
for (int i = head[u]; i; i = edges[i].next) {
int v = edges[i].to;
if (dfs_num[v] == 0) {
dfs(v);
dfs_low[u] = min(dfs_low[u], dfs_low[v]);
} else if (visited[v]) {
dfs_low[u] = min(dfs_low[u], dfs_num[v]);
}
}
if (dfs_low[u] == dfs_num[u]) {
++scc_count;
int v;
do {
v = s.top();
s.pop();
visited[v] = false;
scc[v] = scc_count;
} while (v != u);
}
}
// 求强连通分量的函数
void sccTarjan(int n) {
for (int i = 1; i <= n; ++i) {
if (dfs_num[i] == 0) {
dfs(i);
}
}
}
int main() {
// 读入节点数和边数
int n, m;
cin >> n >> m;
// 读入边
for (int i = 1; i <= m; ++i) {
int u, v;
cin >> u >> v;
addEdge(u, v);
}
// 求强连通分量
sccTarjan(n);
// 输出强连通分量
for (int i = 1; i <= n; ++i) {
cout << "Node " << i << " is in SCC " << scc[i] << endl;
}
return 0;
}
```
该程序使用 Tarjan 算法求解有向图的强连通分量。首先通过邻接表存储有向图,然后使用 dfs 函数遍历每个节点,并记录 dfs_num 和 dfs_low 数组。如果 dfs_low[u] 等于 dfs_num[u],则将 u 节点及其在栈中的祖先节点都出栈,并将它们标记为同一个强连通分量。最后输出每个节点所在的强连通分量编号。
阅读全文