本文共 1292 字，大约阅读时间需要 4 分钟。
问题描述
小明的实验室有N台电脑，编号1~N。原本这N台电脑之间有N-1条数据链接相连，恰好构成一个树形网络。在树形网络上，任意两台电脑之间有唯一的路径相连。
不过在最近一次维护网络时，管理员误操作使得某两台电脑之间增加了一条数据链接，于是网络中出现了环路。环路上的电脑由于两两之间不再是只有一条路径，使得这些电脑上的数据传输出现了BUG。 为了恢复正常传输。小明需要找到所有在环路上的电脑，你能帮助他吗？输入格式
第一行包含一个整数N。
以下N行每行两个整数a和b，表示a和b之间有一条数据链接相连。 对于30%的数据，1 <= N <= 1000 对于100%的数据, 1 <= N <= 100000， 1 <= a, b <= N 输入保证合法。输出格式
按从小到大的顺序输出在环路上的电脑的编号，中间由一个空格分隔。
样例输入
5
1 2 3 1 2 4 2 5 5 3样例输出
1 2 3 5
建立无向图，然后将度<=1的纳入队列，并将与它相连的顶点的度数相应减一，然后再检测<=1的，重复步骤。
那些没有被纳入队列的点形成的边可以组成一个回路。
#include#include #include #include #include using namespace std;const int maxn=1e5+5;int n;int head[maxn];int ans[maxn];int vis[maxn];int du[maxn];int flag=0;int num;struct edge{ int to; int next;}edge[maxn<<1];void add (int id,int u,int v){ edge[id].to=v; edge[id].next=head[u]; head[u]=id;}void judge(int x){ queue q; q.push(x); vis[x]=1; while (!q.empty()) { int now=q.front(); q.pop(); for (int i=head[now];i!=-1;i=edge[i].next) { int t=edge[i].to; du[t]--; if(!vis[t]&&du[t]<=1) { q.push(t); vis[t]=1; num--; } } }}int main(){ memset (head,-1,sizeof(head)); memset (vis,0,sizeof(vis)); memset (du,0,sizeof(du)); scanf("%d",&n); if(n==1) { printf("1\n"); return 0; } for (int i=0,id=0;i
转载地址：http://kwoen.baihongyu.com/