12.5 concurrent search + violent DFS - [discovery ring]

Title Description

Xiao Ming's lab has N Computers , Number 1…N. Originally this N There are... Between computers N-1 A data link , Just form a tree network . On a tree network , There is a unique path between any two computers .

But the last time I maintained the network , The administrator's misoperation caused a data link to be added between two computers , So there is a loop in the network . There is no longer only one path between two computers on the loop , This makes the data transmission on these computers appear BUG.

In order to resume normal transmission . Xiao Ming needs to find all the computers on the loop , Can you help him ？

Input description

Output description

Output the number of computers on the loop in descending order , Separated by a space in the middle .

I/o sample

Input ：

5
1 2
3 1
2 4
2 5
5 3

Output ：

1 2 3 5

---

The final code

1. c/c++

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+1100;
// Container array 
vector<int> vt[N];
int s[N],vis[N],circle[N];
int start,flag,num;

void init_set(){
    
    for(int i=1;i<=N;i++)   s[i]=i;
}
int find_set(int x){
     // Looking for ancestors 
    if(x!=s[x])  s[x]=find_set(s[x]);  // Path compression 
    return s[x];
}
void merge_set(int x,int y){
    
    int tmp = x;
    x = find_set(x);
    y = find_set(y);
    if(x!=y) s[y]=s[x];
    else     start = tmp; // this x and y In the ring , Record a point 
}


void dfs(int x,int step)
{
     // From the starting point start Set out to find a way back to start The loop of 
    if(flag)    return;
    
    if(x==start) // After a circle, I came back , End of loop 
        if(vis[x]==1)
        {
    
            num = step-1;
            flag = 1;
            return ;
        }
        
    circle[step] = x;
    
    
    for(int i=0;i<vt[x].size();i++)   
    {
    
        int y=vt[x][i];
        if(!vis[y])
        {
    
            vis[y]=1;
            dfs(y,step+1);
            vis[y]=0;
        }
    }
}
int main(){
    
   int n;
    scanf("%d",&n);
    init_set();
    for(int i=1;i<=n;i++) 
    {
    
        int a,b;
        scanf("%d %d",&a,&b);
        // Build a two-dimensional container 
        vt[a].push_back(b);
        vt[b].push_back(a);
        merge_set(a,b);  // Find a point on the ring start
    }
    flag = 0;
    // With start Search again for the starting point , This is the ring 
    dfs(start,1);
    
    
    
    sort(circle+1,circle+1+num);
    for(int i=1;i<=num;i++)
        printf("%d ",circle[i]);
    return 0;
}

---

Process understanding