2017第八届蓝桥杯决赛 发现环（伪*拓扑排序）（蓝桥模板）（输出环）

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
typedef long long LL;
const int N=1e5+10;
vector<int> G[N];
queue<int> q;
bool vis[N];
int du[N];

int main(){
	int n,x,y;
	cin>>n;
	for(int i=0;i<n;i++){
		scanf("%d%d",&x,&y);
		G[x].push_back(y);
		G[y].push_back(x);
		du[x]++;
		du[y]++;
	}
	for(int i=1;i<=n;i++){
		if(du[i]==1){
			q.push(i);
			du[i]--;
			vis[i]=1;
		}
	}
	while(!q.empty()){
		int u=q.front();
		q.pop();
		int l=G[u].size();
		for(int i=0;i<l;i++){
			int te=G[u][i];
			if(vis[te]==1) continue;
			du[te]--;
			if(du[te]==1){
				q.push(te);
				vis[te]=1;
			}
		}
	}
	int k;
	for(k=1;k<=n;k++){
		if(vis[k]==0){
		 printf("%d",k);
		 break;	
		}
		}
		for(++k;k<=n;k++){
			if(vis[k]==0) printf(" %d",k);
		}
		printf("\n");
	
}