1067: 有向图的邻接表存储强连通判断

本文主要是介绍1067: 有向图的邻接表存储强连通判断，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

解法：

定理：有向图G是强连通图的充分必要条件是G中存在一条经过所有节点的回路

跟上道题一样

这是错误代码

#include<iostream>
#include<vector>
using namespace std;
int arr[100][100];
void dfs(vector<bool>& a,int u) {a[u] = true;for (int i = 0; i < a.size(); i++) {if (arr[u][i] && !a[i])dfs(a, i);}
}
int main() {int n, e;cin >> n >> e;vector<bool> vis(n, false);while (e--) {int x, y;cin >> x >> y;arr[x][y] = 1;}dfs(vis, 0);for (int i = 0; i < vis.size(); i++) {if (!vis[i]) {cout << "no";return 0;}}cout << "yes";return 0;
}

要搜完所有的节点，还要验证回路

回路用从每个节点出发能搜完所有节点处理

#include<iostream>
#include<vector>
using namespace std;
int arr[100][100];
int cnt;
void dfs(vector<int>& a,int u) {a[u] = 1;cnt++;for (int i = 0; i < a.size(); i++) {if (arr[u][i] && !a[i]) {dfs(a, i);}}
}
int main() {int n, e;cin >> n >> e;vector<int> vis(n, 0);while (e--) {int x, y;cin >> x >> y;arr[x][y] = 1;}for (int i = 0; i < n; i++) {cnt = 0;for (int& x : vis) x = 0;dfs(vis, i);if (cnt != n) {cout << "no";return 0;}}cout << "yes";return 0;
}

这篇关于1067: 有向图的邻接表存储强连通判断的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---