用C++编写一段程序,实现以下功能:输出一个有向图中的强连通分量,并给出测试用例
时间: 2023-12-10 13:42:12 浏览: 74
以下是一个输出有向图中强连通分量的程序,使用深度优先搜索算法实现:
```c++
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
void dfs1(int v, vector<vector<int>>& adj_list, vector<bool>& visited, stack<int>& s) {
visited[v] = true;
for (int u : adj_list[v]) {
if (!visited[u]) {
dfs1(u, adj_list, visited, s);
}
}
s.push(v);
}
void dfs2(int v, vector<vector<int>>& adj_list, vector<bool>& visited, vector<int>& scc) {
visited[v] = true;
scc.push_back(v);
for (int u : adj_list[v]) {
if (!visited[u]) {
dfs2(u, adj_list, visited, scc);
}
}
}
vector<vector<int>> find_scc(vector<vector<int>>& adj_list) {
int n = adj_list.size();
vector<vector<int>> scc_list;
vector<bool> visited(n, false);
stack<int> s;
// 第一次深度优先搜索
for (int i = 0; i < n; i++) {
if (!visited[i]) {
dfs1(i, adj_list, visited, s);
}
}
// 反转图
vector<vector<int>> reversed_adj_list(n, vector<int>());
for (int i = 0; i < n; i++) {
for (int j : adj_list[i]) {
reversed_adj_list[j].push_back(i);
}
}
// 第二次深度优先搜索
visited.assign(n, false);
while (!s.empty()) {
int v = s.top();
s.pop();
if (!visited[v]) {
vector<int> scc;
dfs2(v, reversed_adj_list, visited, scc);
scc_list.push_back(scc);
}
}
return scc_list;
}
int main() {
// 构建有向图
vector<vector<int>> adj_list = {
{1, 2},
{2, 4},
{3, 0},
{4, 5},
{5, 3},
{6, 5},
{6, 7},
{7, 6}
};
// 查找强连通分量
vector<vector<int>> scc_list = find_scc(adj_list);
// 输出结果
for (auto& scc : scc_list) {
cout << "Strongly connected component: ";
for (int v : scc) {
cout << v << " ";
}
cout << endl;
}
return 0;
}
```
测试用例:
输入有向图的邻接表(使用vector表示):
```c++
vector<vector<int>> adj_list = {
{1, 2},
{2, 4},
{3, 0},
{4, 5},
{5, 3},
{6, 5},
{6, 7},
{7, 6}
};
```
输出结果:
```
Strongly connected component: 1 2 4
Strongly connected component: 0 3 5
Strongly connected component: 6 7
```
阅读全文