1.16 learning summary

I wrote one today And look up the title of the collection . It is also a simple understanding , The basic of union search set application . Personally, I think and search for , It's better to understand . This topic is described as follows .

  This should be regarded as the template question of the parallel search set , I am here b Station to learn and search the set of   When .  I also use this type of questions to do   Example . The core idea is still on the compressed path .  With a recursion, all elements with the same ancestry , Put them in The tag   As a common ancestor .  The code is as follows

 #include<stdio.h>
 
int n,m,q,f[10010],c,d,a,b;
int find(int x) 
{
	if(f[x]==x){
    
     
	return x;}
	else {
	  f[x]=find(f[x]);
	  return f[x];} 
    
}
void hb(int x,int y)
{
	f[find(x)]=find(y); 
   
	return ;
}
int main()
{
	scanf("%d%d%d",&n,&m,&q);
	for(int i=1;i<=n;i++){
	f[i]=i;}
	for(int i=1;i<=m;i++)
	{
	     scanf("%d%d",&c,&d);
	     hb(c,d);
	}
	for(int i=1;i<=q;i++)
	{
		scanf("%d%d",&a,&b);
		if(find(a)==find(b)) 
		printf("Yes\n");
		else
		printf("No\n");
	}
	return 0;
}

And the compressed path of the core   The code is the next paragraph .

int find(int x) 
{
	if(f[x]==x){
    
     
	return x;}
	else {
	  f[x]=find(f[x]);
	  return f[x];} 
    
}

Among them, this recursion is to integrate all common ancestors . All the values of the element are assigned to that ancestor, that is, the compression path .

Today's learning summary , That's it .