Joint set search: merge intervals and ask whether two numbers are in the same set

 

Merge ：

 

Path compression ：

#include<iostream>
using namespace std;

const int N=100010;

int n,m;
int p[N];

// return x The ancestor node of + Path compression 
// Path compression ： Point each node to its ancestor node  
int find(int x)
{
	if(p[x]!=x)
		p[x]=find(p[x]);
	return p[x];
}

int main()
{
	scanf("%d%d",&n,&m);
	
	// initialization ： Point the ancestor node of each node to itself  
	for(int i=1;i<=n;i++)
		p[i]=i;
	
	while(m--)
	{
		char op[2];
		int a,b;
		scanf("%s%d%d",op,&a,&b);
		
		if(op[0]=='M')// Merge nodes   
			p[find(a)]=find(b);
		else
		{
			if(find(a)==find(b))
				puts("Yes");
			else
				puts("No");
		}
	}
	
	return 0;
}