这个问题一直没仔细写过,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;
}