金溪做网站/上海搜索引擎优化seo

题目

给你一棵N个节点的树，

并多加一条边，也就是N条边

要你输出图中唯一的一个环，

即按增序输出环上点的标号

1<=N<=100000

思路来源

http://www.cnblogs.com/shoulinniao/p/10423674.html

题解

本来被自己dfs瞎搞搞过去了

但想到topo也挺重要的，之前敲得也不多

之前一般是用于有向图的情形，现在发现无向图也可以用

有向图是每次找到入度为0的点，然后删去对应边的入度，最后入度>=1的即为所求

无向图是每次找到度为1的点，然后删去对应边的度，最后度>=2的即为所求

代码1（dfs判环+找环）

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
using namespace std;
typedef long long ll;
const int maxn=1e5+10;
int n,head[maxn],cnt; 
int in[maxn],u,v;
int loop;
vector<int>ans;
bool flag;
struct edge
{int v,nex;
}e[maxn*2];
void add(int u,int v)
{e[++cnt].v=v;e[cnt].nex=head[u];head[u]=cnt; 
}
void dfs(int u,int fa)
{in[u]=1;for(int i=head[u];i;i=e[i].nex){int v=e[i].v;if(v==fa)continue;if(!in[v])dfs(v,u);else if(in[v]==1){loop=v;flag=1;}if(flag)break;}if(flag){ans.push_back(u);if(u==loop)flag=0;}in[u]=2;
}
int main()
{    scanf("%d",&n);for(int i=1;i<=n;++i){scanf("%d%d",&u,&v);add(u,v);add(v,u);}dfs(1,-1);sort(ans.begin(),ans.end());int len=ans.size();for(int i=0;i<len;++i)printf("%d%c",ans[i],i==len-1?'\n':' ');return 0;
}

代码2（topo判环）

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
const int maxn=1e5+10;
int n,a,b,cnt;
int in[maxn];
vector<int>e[maxn];
queue<int>q;
bool vis[maxn];
void topo()
{for(int i=1;i<=n;++i){if(in[i]==1){q.push(i);vis[i]=1; } }while(!q.empty()){int t=q.front(); q.pop();int len=e[t].size();for(int i=0;i<len;++i){if((--in[e[t][i]])==1){q.push(e[t][i]);vis[e[t][i]]=1;}}}
}
int main()
{scanf("%d",&n);for(int i=1;i<=n;++i){scanf("%d%d",&a,&b);e[a].push_back(b);in[b]++;e[b].push_back(a);in[a]++;}topo();for(int i=1;i<=n;++i)if(!vis[i]){if(!cnt)printf("%d",i);else printf(" %d",i);cnt++;}puts("");return 0;
}