赞
踩
这个问题一直没仔细写过,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;
- }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。