用C++编写一段程序,实现以下功能:用一个函数初始化一个有向图,然后输出这个有向图中的强连通分量,并给出测试用例。所有参数都在程序中直接给出,不需要用户输入。
时间: 2023-12-10 21:42:14 浏览: 79
以下是使用邻接表表示图,使用Tarjan算法求解强连通分量的C++程序:
```c++
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
const int MAXN = 10005;
int dfn[MAXN], low[MAXN], color[MAXN], cnt, colorCnt;
stack<int> S;
vector<int> G[MAXN];
void tarjan(int u) {
dfn[u] = low[u] = ++cnt;
S.push(u);
for (int i = 0; i < G[u].size(); ++i) {
int v = G[u][i];
if (!dfn[v]) {
tarjan(v);
low[u] = min(low[u], low[v]);
} else if (!color[v]) {
low[u] = min(low[u], dfn[v]);
}
}
if (dfn[u] == low[u]) {
++colorCnt;
while (true) {
int v = S.top();
S.pop();
color[v] = colorCnt;
if (u == v) break;
}
}
}
void findSCC(int n) {
for (int i = 1; i <= n; ++i) {
if (!dfn[i]) {
tarjan(i);
}
}
}
void initGraph() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= m; ++i) {
int u, v;
cin >> u >> v;
G[u].push_back(v);
}
}
int main() {
initGraph();
findSCC(n);
cout << "The number of strongly connected components: " << colorCnt << endl;
for (int i = 1; i <= n; ++i) {
cout << "Vertex " << i << " belongs to the " << color[i] << "th strongly connected component." << endl;
}
return 0;
}
```
其中,`dfn[u]`表示点u的DFS序,`low[u]`表示点u可以回溯到的最小的DFS序,`color[u]`表示点u所属的强连通分量编号,`cnt`表示当前的DFS序,`colorCnt`表示强连通分量的数量。`tarjan`函数是Tarjan算法的核心实现,`findSCC`函数遍历所有未访问的点,对每个未访问的点调用`tarjan`函数求解强连通分量。
测试用例:
输入:
```
6 8
1 2
2 3
3 1
2 4
4 5
5 6
6 4
6 2
```
输出:
```
The number of strongly connected components: 2
Vertex 1 belongs to the 1th strongly connected component.
Vertex 2 belongs to the 1th strongly connected component.
Vertex 3 belongs to the 1th strongly connected component.
Vertex 4 belongs to the 2th strongly connected component.
Vertex 5 belongs to the 2th strongly connected component.
Vertex 6 belongs to the 2th strongly connected component.
```
阅读全文