问题描述 小明的实验室有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
//深搜的典型题目 #include <iostream> #include <cstring> #include <algorithm> #include <vector> using namespace std; int N; vector<int> G[100005]; //用向量保存邻接表 int Vis[100005]; //判断是否遍历过 int dfs(int Father,int u) //父节点和当前节点 { Vis[u]=1; //当前结点默认查询过 int flag=0; int flag1=0; int Findnod = 0; // 返回上一层的查询结果 int Find=0; // 查询中间结果 for(int i=0;i<G[u].size();i++) { if(Vis[G[u][i]]==0&&G[u][i]!=Father) { Find=dfs(u,G[u][i]); //dfs深搜 if(Find!=0&&Find!=u&&flag1==0) //如果查到重复的结点并且查到的结点不是当前结点，且已经运行了这个一次 { // printf("father:%d find:%d now:%d\n",Father,Find,u); Vis[u]++; //当前结点必定处于环上 flag1=1; //不必进行下一次的操作 Findnod=Find; //说明有不为0的查询结果 } if(Find==u) //如果查询的结果等于当前的结果则说明已经返回到环的根结点 { Findnod=0; //状态归0 } } else if(Vis[G[u][i]]==1&&G[u][i]!=Father) //这里查询连接到根结点的条件 { Vis[u]++; //当前节点加一 Vis[G[u][i]]++; //根结点加一 // printf("father:%d u:%d Find:%d \n",Father,u,G[u][i]); Findnod=G[u][i]; //发现环 ，向上一层返回根结点 //flag=1; //表名查到 } } return Findnod; } int main() { scanf("%d",&N); int A,B; for(int i = 0;i<N;i++) { cin>>A>>B; G[A].push_back(B); G[B].push_back(A); } memset(Vis,0,sizeof(Vis)); dfs(0,1); for(int i =1;i<=N;i++) { if(Vis[i]>1) { printf("%d ",i); } } return 0; }