用C++编写一段程序,实现以下功能:用一个函数初始化一个有向图,然后输出这个有向图中的强连通分量,并给出测试用例
时间: 2023-12-10 19:42:13 浏览: 95
实验_C++_数据结构_图连通分量_
5星 · 资源好评率100%
以下是用C++编写的程序,实现了初始化一个有向图并输出其中的强连通分量:
```cpp
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
// 初始化有向图
void initGraph(vector<int> adjList[], int V, int E, int edges[][2]) {
for(int i = 0; i < E; i++) {
int u = edges[i][0];
int v = edges[i][1];
adjList[u].push_back(v);
}
}
// 深度优先搜索,求解强连通分量
void DFS(vector<int> adjList[], int u, bool visited[], stack<int>& st) {
visited[u] = true;
for(int v : adjList[u]) {
if(!visited[v]) {
DFS(adjList, v, visited, st);
}
}
st.push(u);
}
// 反向图进行深度优先搜索
void reverseDFS(vector<int> revAdjList[], int u, bool visited[]) {
visited[u] = true;
cout << u << " ";
for(int v : revAdjList[u]) {
if(!visited[v]) {
reverseDFS(revAdjList, v, visited);
}
}
}
// 找到强连通分量
void findSCC(vector<int> adjList[], vector<int> revAdjList[], int V) {
bool visited[V];
// 初始化visited数组
for(int i = 0; i < V; i++) {
visited[i] = false;
}
stack<int> st;
// 对每个未访问的节点进行深度优先搜索,将访问到的节点压入栈中
for(int i = 0; i < V; i++) {
if(!visited[i]) {
DFS(adjList, i, visited, st);
}
}
// 初始化visited数组
for(int i = 0; i < V; i++) {
visited[i] = false;
}
// 反向图进行深度优先搜索,找到强连通分量
while(!st.empty()) {
int u = st.top();
st.pop();
if(!visited[u]) {
cout << "SCC: ";
reverseDFS(revAdjList, u, visited);
cout << endl;
}
}
}
int main() {
int V = 5;
int E = 7;
int edges[][2] = {{0, 1}, {1, 2}, {2, 0}, {1, 3}, {3, 4}, {4, 3}, {4, 2}};
vector<int> adjList[V];
vector<int> revAdjList[V];
initGraph(adjList, V, E, edges);
// 构建反向图
for(int i = 0; i < V; i++) {
for(int v : adjList[i]) {
revAdjList[v].push_back(i);
}
}
findSCC(adjList, revAdjList, V);
return 0;
}
```
测试用例:
输入:
```cpp
int V = 5;
int E = 7;
int edges[][2] = {{0, 1}, {1, 2}, {2, 0}, {1, 3}, {3, 4}, {4, 3}, {4, 2}};
```
输出:
```
SCC: 0 2 1
SCC: 3 4
```
阅读全文