1.17 learning summary

Today, I wrote a lot of questions about searching the collection . It is also useful for the union search set And some uses have been recognized . What I have used today are two kinds . One is Using the same ancestor of the element To solve some problems . There's another one , Use the number of ancestors to solve some problems . The first one is basically the template problem of joint search set .

For example, this question .

  This question is a standard template . Is a merge set   Then you can . Judging whether it is the same ancestor can solve this problem . The code is as follows ,

 #include<stdio.h>
 int i,j,k,n,m,s,ans,a[10010],b,c,d;
 
 int find(int k){
  
     if(a[k]==k)return k;
      a[k]=find(a[k]);
      return a[k];
 }
 int main()
 {
     scanf("%d%d",&n,&m);
     for(i=1;i<=n;i++)
         a[i]=i; 
     for(i=1;i<=m;i++){
         scanf("%d %d %d",&b,&c,&d);
         if(b==1)
             a[find(c)]=find(d);
            
        if(b==2){
             if(find(c)==find(d))
             
                 printf("Y\n");
             else
                 printf("N\n");
     }}
     return 0;
 }

Then I said that the other way I used to solve problems was based on the number of ancestors .

The title is as follows .

  What is required here is at least the disc to be recorded . In essence, it means that I have experienced the following . After union operation , There are also several ancestors . in other words , Our ancestors are our own   Elements . 

The code is as follows

  #include<stdio.h>
 int a[300];
 int  vis[300][300];             
 int main()
 {
 	int n,t,ans=0;
 	scanf("%d",&n);
 	for(int i=1;i<=n;i++)
 	{
 		t=0;
 		while(t!=-1)
 		{
		 	scanf("%d",&t);
		 	if(t!=0){
 			vis[i][t]=1;}
 			if(t==0){
			 	break;
			 }
			        
 		}
 	}
 	for(int i=1;i<=n;++i)
 	a[i]=i;                 
 	for(int k=1;k<=n;++k)
 	for(int i=1;i<=n;++i)
 	for(int j=1;j<=n;++j)
 		if(vis[i][k]==1&&vis[k][j]==1)
 		  vis[i][j]=1;              
 	for(int i=1;i<=n;++i)
 	for(int j=1;j<=n;++j)
 	if(vis[i][j]==1)
 	a[j]=a[i];
 	for(int i=1;i<=n;++i)
 	if(a[i]==i)
 	ans++;                      
 	printf("%d",ans);
 	return 0;                  
 } 

But this problem can not be solved by an ordinary joint search set .  Because this question is one-way .  The ordinary union search set is bidirectional . So this problem just uses an idea similar to the union search set .  What I chose was to use a two-dimensional array to record all the related objects . Then use a three-level nesting for loop .  To put all that have a continuous relationship   Elements ,  Make contact .  For example, one and two are related , Two and three are related . Then it will be linked . After that, we will traverse this   Two dimensional array .   Mark the corresponding ancestral relationship . Then iterate over the one-dimensional array used as a marker . You can get that all ancestors are their own . Element this element is the number of discs to burn . This is how I think about this question . The time complexity of this algorithm is relatively high . But it's okay , The data range given by this question is relatively small , So it can also pass .

The above is the summary of today's study .