Connected graph (union search set)

int find(int x) // Find the root node （ Find the leader ）
{
    if(pre[x] != find(x)) pre[x] = find(pre[x]);
    return pre[x];
}

Example ： Union checking set

Given an undirected graph and all its edges , Determine whether all vertices of the graph are connected .

Input format

The input contains several sets of data .

The first row of each set of data contains two integers  nn  and  mm, Represents the number of points and edges of an undirected graph .

Next  mm  That's ok , Each line contains two integers  x,yx,y, Indication point  xx  Sum point  yy  Connected to a .

The number of the point is from  11  To  nn.

There may be double edges and self rings in the graph .

Output format

Output one row per group of data , A result , If all the vertices are connected , Output  YES, Otherwise output  NO.

Data range

The input can contain at most  1010  Group data .
1≤n≤10001≤n≤1000,
1≤m≤50001≤m≤5000,
1≤x,y≤n1≤x,y≤n

sample input ：

4 3
1 2
2 3
3 2
3 2
1 2
2 3

sample output ：

NO
YES

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N=1010;
int pre[N];

int find(int x)
{
    if(pre[x]!=x) pre[x]=find(pre[x]);
    return pre[x];
}

int main()
{
    int n,m,a,b;
    while(cin>>n>>m)
    {
        for(int i=1;i<=n;i++) pre[i]=i;
        
        while(m--)
        {
            cin>>a>>b;
            pre[find(a)]=find(b);
        }
        
        bool res=true;
        for(int i=2;i<=n;i++)
        {
            if(find(i)!=find(1))
                res=false;
        }
        
        if(res) puts("YES");
        else puts("NO");
    }
    return 0;
}

 2022/7/11