Detail of message

Online Judge

Problem Set

Authors

Online Contests

User

Web Board
Home Page
F.A.Qs
Statistical Charts

Current Contest
Past Contests
Scheduled Contests
Award Contest

并查集，不容易啊！研究了两天总算搞明白了。

Posted by wangbaobao at 2009-05-19 17:21:32 on Problem 1703

#include"iostream"
using namespace std;
#define MAX 100010
int father[MAX];
int opp[MAX];
void make_set(int num_bug)
{
	int i;
	for(i=1;i<=num_bug;i++)   //  就差着了，记着在这下标必须从1开始
	{
		father[i]=-1;               
	                               
		opp[i]=-1;                  
	}
}
int find_set(int x)
{
	if(father[x]<0)
	{
		return x;
	}
return father[x]=find_set(father[x]);
}
int union_set(int first, int second)
{
    int i, j;
    if(second == -1)
        return first;

    i = find_set(first);
    j = find_set(second);
    if(i == j)
        return i;
    if(father[i] < father[j])
    {
        father[i] += father[j];
        father[j] = i;
        return i;
    }
    else
    {
        father[j] += father[i];
        father[i] = j;
        return j;
    }
   // return -1;
}

int main()
{
	int T;

    int num_bug;
    int num_message;
	char signal;
    int x,y;
	cin>>T;
	while(T--)
	{
		
        cin>>num_bug>>num_message;
        make_set(num_bug);
        for(int i=0;i<num_message;i++)
		{
			
			 getchar();                // 搞不懂这为啥要加getchar();
			 scanf("%c",&signal);			 
			 scanf("%d %d",&x,&y);
			
			  if(signal=='D')
			  {
				  
				   
				  
				  
				  
				  int aa,bb,a,b;
				  aa=find_set(x);
				  bb=find_set(y);
				  
				  if(opp[bb]!=-1&&opp[aa]==-1)
				  {
					  a=union_set(aa,opp[bb]);
                      opp[a]=bb;
				      opp[bb]=a;
				  }
  
				  else if(opp[aa]!=-1&&opp[bb]==-1)
				  {
					  b=union_set(bb,opp[aa]);
					  opp[b]=aa;
				      opp[aa]=b;
				  }
				  else if(opp[aa]==-1&&opp[bb]==-1)
				  {
					  opp[aa]=bb;
					  opp[bb]=aa;
				  }
				  else if(opp[aa]!=-1&&opp[bb]!=-1)
				  {
					  a=union_set(aa,opp[bb]);
					  b=union_set(bb,opp[aa]);
                      opp[a]=b;
					  opp[b]=a;
				  }
		}
			 else
			 {
				 
			     int aa,bb;
				 aa=find_set(x);
				 bb=find_set(y);
				 if(aa==bb)
				       printf("In the same gang.\n"); 
					 
			      else
				  {
				       if(opp[aa]==bb)
					       printf("In different gangs.\n");
						   
			           else
					       printf("Not sure yet.\n");
						
				  }

			}
		}
	}
	return 1;
}
、*************************************************************************
		
#include"iostream"
using namespace std;
#define MAX 100010
int father[MAX];
int opp[MAX];
void make_set(int num_bug)
{
	int i;
	for(i=1;i<=num_bug;i++)   //  就差着了，记着在这下标必须从1开始
	{
		father[i]=-1;               
	                               
		opp[i]=-1;                  
	}
}
int find_set(int x)
{
	if(father[x]<0)
	{
		return x;
	}
return father[x]=find_set(father[x]);
}
int union_set(int first, int second)
{
    int i, j;
    if(second == -1)
        return first;

    i = find_set(first);
    j = find_set(second);
    if(i == j)
        return i;
    if(father[i] < father[j])
    {
        father[i] += father[j];
        father[j] = i;
        return i;
    }
    else
    {
        father[j] += father[i];
        father[i] = j;
        return j;
    }
   // return -1;
}

int main()
{
	int T;

    int num_bug;
    int num_message;
	char signal;
    int x,y;
	cin>>T;
	while(T--)
	{
		
        cin>>num_bug>>num_message;
        make_set(num_bug);
        for(int i=0;i<num_message;i++)
		{
			
			 getchar();                // 搞不懂这为啥要加getchar();
			 scanf("%c",&signal);			 
			 scanf("%d %d",&x,&y);
			
			  if(signal=='D')
			  {
				  
				   
				  
				  
				  
				  int aa,bb,a,b;
				  aa=find_set(x);
				  bb=find_set(y);
				  
				  if(opp[bb]!=-1&&opp[aa]==-1)
				  {
					  a=union_set(aa,opp[bb]);
                      opp[a]=bb;
				      opp[bb]=a;
				  }
  
				  else if(opp[aa]!=-1&&opp[bb]==-1)
				  {
					  b=union_set(bb,opp[aa]);
					  opp[b]=aa;
				      opp[aa]=b;
				  }
				  else if(opp[aa]==-1&&opp[bb]==-1)
				  {
					  opp[aa]=bb;
					  opp[bb]=aa;
				  }
				  else if(opp[aa]!=-1&&opp[bb]!=-1)
				  {
					  a=union_set(aa,opp[bb]);
					  b=union_set(bb,opp[aa]);
                      opp[a]=b;
					  opp[b]=a;
				  }
		}
			 else
			 {
				 
			     int aa,bb;
				 aa=find_set(x);
				 bb=find_set(y);
				 if(aa==bb)
				       printf("In the same gang.\n"); 
					 
			      else
				  {
				       if(opp[aa]==bb)
					       printf("In different gangs.\n");
						   
			           else
					       printf("Not sure yet.\n");
						
				  }

			}
		}
	}
	return 1;
}

Followed by:

Post your reply here:

User ID:
Password:
Title:

Content:

> #include"iostream"
> using namespace std;
> #define MAX 100010
> int father[MAX];
> int opp[MAX];
> void make_set(int num_bug)
> {
> 	int i;
> 	for(i=1;i<=num_bug;i++)   //  就差着了，记着在这下标必须从1开始
> 	{
> 		father[i]=-1;               
> 	                               
> 		opp[i]=-1;                  
> 	}
> }
> int find_set(int x)
> {
> 	if(father[x]<0)
> 	{
> 		return x;
> 	}
> return father[x]=find_set(father[x]);
> }
> int union_set(int first, int second)
> {
>     int i, j;
>     if(second == -1)
>         return first;
> 
>     i = find_set(first);
>     j = find_set(second);
>     if(i == j)
>         return i;
>     if(father[i] < father[j])
>     {
>         father[i] += father[j];
>         father[j] = i;
>         return i;
>     }
>     else
>     {
>         father[j] += father[i];
>         father[i] = j;
>         return j;
>     }
>    // return -1;
> }
> 
> int main()
> {
> 	int T;
> 
>     int num_bug;
>     int num_message;
> 	char signal;
>     int x,y;
> 	cin>>T;
> 	while(T--)
> 	{
> 		
>         cin>>num_bug>>num_message;
>         make_set(num_bug);
>         for(int i=0;i<num_message;i++)
> 		{
> 			
> 			 getchar();                // 搞不懂这为啥要加getchar();
> 			 scanf("%c",&signal);			 
> 			 scanf("%d %d",&x,&y);
> 			
> 			  if(signal=='D')
> 			  {
> 				  
> 				   
> 				  
> 				  
> 				  
> 				  int aa,bb,a,b;
> 				  aa=find_set(x);
> 				  bb=find_set(y);
> 				  
> 				  if(opp[bb]!=-1&&opp[aa]==-1)
> 				  {
> 					  a=union_set(aa,opp[bb]);
>                       opp[a]=bb;
> 				      opp[bb]=a;
> 				  }
>   
> 				  else if(opp[aa]!=-1&&opp[bb]==-1)
> 				  {
> 					  b=union_set(bb,opp[aa]);
> 					  opp[b]=aa;
> 				      opp[aa]=b;
> 				  }
> 				  else if(opp[aa]==-1&&opp[bb]==-1)
> 				  {
> 					  opp[aa]=bb;
> 					  opp[bb]=aa;
> 				  }
> 				  else if(opp[aa]!=-1&&opp[bb]!=-1)
> 				  {
> 					  a=union_set(aa,opp[bb]);
> 					  b=union_set(bb,opp[aa]);
>                       opp[a]=b;
> 					  opp[b]=a;
> 				  }
> 		}
> 			 else
> 			 {
> 				 
> 			     int aa,bb;
> 				 aa=find_set(x);
> 				 bb=find_set(y);
> 				 if(aa==bb)
> 				       printf("In the same gang.\n"); 
> 					 
> 			      else
> 				  {
> 				       if(opp[aa]==bb)
> 					       printf("In different gangs.\n");
> 						   
> 			           else
> 					       printf("Not sure yet.\n");
> 						
> 				  }
> 
> 			}
> 		}
> 	}
> 	return 1;
> }
> 、*************************************************************************
> 		
> #include"iostream"
> using namespace std;
> #define MAX 100010
> int father[MAX];
> int opp[MAX];
> void make_set(int num_bug)
> {
> 	int i;
> 	for(i=1;i<=num_bug;i++)   //  就差着了，记着在这下标必须从1开始
> 	{
> 		father[i]=-1;               
> 	                               
> 		opp[i]=-1;                  
> 	}
> }
> int find_set(int x)
> {
> 	if(father[x]<0)
> 	{
> 		return x;
> 	}
> return father[x]=find_set(father[x]);
> }
> int union_set(int first, int second)
> {
>     int i, j;
>     if(second == -1)
>         return first;
> 
>     i = find_set(first);
>     j = find_set(second);
>     if(i == j)
>         return i;
>     if(father[i] < father[j])
>     {
>         father[i] += father[j];
>         father[j] = i;
>         return i;
>     }
>     else
>     {
>         father[j] += father[i];
>         father[i] = j;
>         return j;
>     }
>    // return -1;
> }
> 
> int main()
> {
> 	int T;
> 
>     int num_bug;
>     int num_message;
> 	char signal;
>     int x,y;
> 	cin>>T;
> 	while(T--)
> 	{
> 		
>         cin>>num_bug>>num_message;
>         make_set(num_bug);
>         for(int i=0;i<num_message;i++)
> 		{
> 			
> 			 getchar();                // 搞不懂这为啥要加getchar();
> 			 scanf("%c",&signal);			 
> 			 scanf("%d %d",&x,&y);
> 			
> 			  if(signal=='D')
> 			  {
> 				  
> 				   
> 				  
> 				  
> 				  
> 				  int aa,bb,a,b;
> 				  aa=find_set(x);
> 				  bb=find_set(y);
> 				  
> 				  if(opp[bb]!=-1&&opp[aa]==-1)
> 				  {
> 					  a=union_set(aa,opp[bb]);
>                       opp[a]=bb;
> 				      opp[bb]=a;
> 				  }
>   
> 				  else if(opp[aa]!=-1&&opp[bb]==-1)
> 				  {
> 					  b=union_set(bb,opp[aa]);
> 					  opp[b]=aa;
> 				      opp[aa]=b;
> 				  }
> 				  else if(opp[aa]==-1&&opp[bb]==-1)
> 				  {
> 					  opp[aa]=bb;
> 					  opp[bb]=aa;
> 				  }
> 				  else if(opp[aa]!=-1&&opp[bb]!=-1)
> 				  {
> 					  a=union_set(aa,opp[bb]);
> 					  b=union_set(bb,opp[aa]);
>                       opp[a]=b;
> 					  opp[b]=a;
> 				  }
> 		}
> 			 else
> 			 {
> 				 
> 			     int aa,bb;
> 				 aa=find_set(x);
> 				 bb=find_set(y);
> 				 if(aa==bb)
> 				       printf("In the same gang.\n"); 
> 					 
> 			      else
> 				  {
> 				       if(opp[aa]==bb)
> 					       printf("In different gangs.\n");
> 						   
> 			           else
> 					       printf("Not sure yet.\n");
> 						
> 				  }
> 
> 			}
> 		}
> 	}
> 	return 1;
> }
> 
> 		
> 
> 
> 
> 
> 
> 
> 
>

Home Page Go Back To top