AcWing 836. Merge set (merge set)

Original link ：https://www.acwing.com/problem/content/838/

subject ：

 

Altogether  n  Number , The number is  1∼n, At first, each number is in a set .

Now it's time to  m  Operations , There are two kinds of operations ：

1. M a b, Will be numbered as  a  and  b  Merge the set of two numbers of , If two numbers are already in the same set , Ignore this operation ;
2. Q a b, The inquiry number is  a  and  b  Whether the two numbers of are in the same set ;

Input format

Enter the integer in the first line  n  and  m.

Next  m  That's ok , Each line contains an operation instruction , Instructions for  M a b  or  Q a b  One of the .

Output format

For each inquiry instruction  Q a b, You have to output a result , If  a  and  b  Within the same set , The output  Yes, Otherwise output  No.

Each result takes up one line .

Data range

1≤n,m≤10^5

sample input ：

4 5
M 1 2
M 3 4
Q 1 2
Q 1 3
Q 3 4

sample output ：

Yes
No
Yes

  Interpretation of parallel search algorithm ：

  Code implementation ：

#include<iostream>
using namespace std;
int n,m;
const int N=100010;
int p[N];
int find(int x)// look for x Our ancestors   Path optimization 
{
    if(p[x]!=x)p[x]=find(p[x]);
    return p[x];
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)p[i]=i;
    while(m--)
    {
        char op;
        int a,b;
        cin>>op>>a>>b;
        if(op=='M')
        {
            p[find(a)]=find(b);//a The ancestor's parent node is equal to b Our ancestors 
        }
        else if(op=='Q'){
            if(find(a)==find(b))cout<<"Yes"<<endl;
            else cout<<"No"<<endl;
        }
    }
    return 0;
}