当前位置: 代码迷 >> 综合 >> 有环图求环的个数和具体节点数
  详细解决方案

有环图求环的个数和具体节点数

热度:45   发布时间:2024-01-16 13:27:17.0

这个问题一直没仔细写过,cf上做到了就写一下,就是用栈存储+回溯,很简单。

#include<iostream>
#include<cstring>
#include<stack>
#include<vector>
#include<algorithm>
using namespace std;
const int N = 20;
vector<int> edge[N];
int s[N],top=0;//stl里的stack没办法遍历,所以用数组模拟
bool instack[N];
int cnt = 0;void dfs(int u)
{s[top++] = u;instack[u] = true;for (int i = 0; i < edge[u].size(); i++){int v = edge[u][i];if (!instack[v])dfs(v);else{printf("第%d个环: ", ++cnt);int t;for (t = top; s[t] != v; t--);for (int i = t; i < top; i++)cout << s[i] << " ";cout << endl;}}top--;		//回溯instack[u] = false;
}int main()
{int n, m,u,v;cin >> n >> m;for (int i = 0; i < m; i++){cin >> u >> v;edge[u].push_back(v);}dfs(1);return 0;
}


  相关解决方案