这是一个拓扑排序的题，用dfs找一下拓扑序列，因为找不到所以一定会有环，记录每一个点的前驱点，所求就是答案
#include<iostream> #include<algorithm> #include<cstring> #include<vector> using namespace std ; const int N = 1e5 +10 ; struct edge{//用于记录边 int from , to ; edge(int a, int b){ from = a , to = b ; } }; int n ,cnt;//n是点的数量 bool v[N] ;//记录是否走过这个点 int path[N] ;//最后记录路径 int flag ;//记录一下是否找到环，找到环就退出dfs，要不然死循环 int fa[N] ;//记录每一个节点的前驱节点，便于后面路径的更新 vector<edge> e[N] ;//记录每一条边 void dfs(int u ,int pre){ v[u] = 1 ;//凡是进来的点都标记一下，而且我们每一个点只会走一遍，如果走到第二遍就表示扎到了环 for(int i = 0 ; i < e[u].size() ; i ++){ int a = e[u][i].from , b = e[u][i].to ;//起点和终点 if(b == pre){//因为是无向边所以我们不能再走上一个节点 continue ; } fa[b] = a ;//记录一下当前这个点的父节点（前驱节点） if(v[b]){//如果找到走了第二次的点，就回溯记录路径 int tmp = b ; flag = 1;//把旗帜标1 ， 表示我们已经找到环了，马上退出dfs while(1){ tmp = fa[tmp]; path[cnt++] = tmp ; if(tmp == b) break ; } return ; } else dfs(b,a) ;//没有找到环，继续深搜遍历每一个点 if(flag == 1) return ; } } int main(){ cin >> n ; for(int i = 0 ; i <n ; i ++){ int a , b ; cin >> a >> b ;//无向图，所以要记录双向 e[a].push_back(edge(a,b)) ; e[b].push_back(edge(b,a)) ; } dfs(1,0) ; sort(path,path + cnt) ;//从大到小排序 for(int i = 0 ; i < cnt ; i ++) { cout << path[i]<< " " ; } cout << endl ; return 0 ; }
