VJudge--Find them, Catch them

Xieyuw

2019-12-01

算法学习

题目 - Find them, Catch them

The police office in Tadu City decides to say ends to the chaos, as launch actions to root up the TWO gangs in the city, Gang Dragon and Gang Snake. However, the police first needs to identify which gang a criminal belongs to. The present question is, given two criminals; do they belong to a same clan? You must give your judgment based on incomplete information. (Since the gangsters are always acting secretly.)

Assume N (N <= 10^5) criminals are currently in Tadu City, numbered from 1 to N. And of course, at least one of them belongs to Gang Dragon, and the same for Gang Snake. You will be given M (M <= 10^5) messages in sequence, which are in the following two kinds:

\1. D [a] [b]
where [a] and [b] are the numbers of two criminals, and they belong to different gangs.

\2. A [a] [b]
where [a] and [b] are the numbers of two criminals. This requires you to decide whether a and b belong to a same gang.

Input

The first line of the input contains a single integer T (1 <= T <= 20), the number of test cases. Then T cases follow. Each test case begins with a line with two integers N and M, followed by M lines each containing one message as described above.

Output

For each message “A [a] [b]” in each case, your program should give the judgment based on the information got before. The answers might be one of “In the same gang.”, “In different gangs.” and “Not sure yet.”

Sample Input

Sample Output

1
2
3

Not sure yet.
In different gangs.
In the same gang

题目大意:

在一个城市里有两种不同的犯罪团伙。首先输入T表示有T组测试，然后输入N和M，表示有N个罪犯（编号从1到N）而且接下来有M个操作。操作分为两种：

1.D a b，表示编号为a和b的两个罪犯属于不同的犯罪团伙；

2.A a b，表示询问编号为a和b的两个罪犯是否是同一个犯罪团伙或者不确定。

对于每一个A操作，根据题意都要有相应的回答（输出）。

思路：

一道标准的关系型并查集题。普通的并查集是给几个同类的元素，而关系型并查集是给不同类的元素，然后求各个元素之间的关系。对于这种题目,我们不仅需要开一个pre[]存父节点,还需要开一个r[]关系数组,来记录其和父亲的关系,r[]=0表示属于同一个帮派,r[]=1，表示不属于同一个帮派，初始化都为同一个帮派。一旦输入x和y不属于同一个帮派就将x和y连通同时更新r[]，一旦输入A，如果find（x）!=find（y）,说明还没输入它们的关系,所以不确定;如果find（x）==find(y）由于r[]数组表示的是该节点和父节点的关系,两个节点又属于同一个节点,所以如果r[x]==r[y]则属于同一个帮派,否则不属于;
处理方法:
1、在利用find函数不断寻找根节点的过程中需要不断更新r[],举个例子:因为我们在利用find函数寻找根节点时有路径压缩,所以我们需要推导出
子节点、父节点、和爷爷节点三者之间的关系:
如果子节点和父节点关系为r1，父节点和爷爷节点关系为r2，那么孙子节点和爷爷节点的关系为（r1+r2）%2;(两种情况所以对2去模)
证明:
我们可以列出所有的可能情况
（a, b） (b, c) (a, c) (r1+r2)%2
0 0 0 0
0 1 1 1
1 0 1 1
1 1 0 0
PS:我个人一开始对为什么子父节点之间的关系会为同一个帮派感到困惑,因为题目中给出的都是不同帮派的,其实仔细一想并不是,我们在合并连通
过程中存在着路径压缩,将孙子节点变为了儿子节点通过上面的关系式就有可能出现相同的情况了;
2、在用join函数就行连通是也需要及时更新r[],我们还是通过推导得出关系式,
假设我们f1为x1的根节点,f2为x2的根节点,我们现在要将f1合并到f2上去, 推导关系式为 r[f1]=(r[x1]+r[x2]+1)%2;
证明:
我们还是罗列出一些情况: 首先需要明确一点的,我们需要合并 x1和x2以为他们两个不是同一个帮派的,所以有x1和x2的关系为1
（x1, f1） (x2, f2) (x1, x2) (f1,f2)_
0 0 1 1
0 1 1 0
1 0 1 0
1 1 1 1

AC代码：

#include<iostream>
using namespace std;
#define N 100010 
int pre[N];
int r[N];
int n,m;
void init() 
{
     for (int i=1;i<=n;i++)       
    {
        pre[i]=i;
              r[i]=0;
    }
     
}
int find(int x) 
{
      if(x==pre[x])      return x;
         int tmp=pre[x];
         pre[x]=find(pre[x]);
         r[x]=(r[x]+r[tmp])%2;
         return pre[x];
        
}
void join(int x1,int x2) 
{
        int f1=find(x1);
        int f2=find(x2);
        if(f1!=f2)     
    {
         pre[f1]=f2;
         r[f1]=(r[x1]+r[x2]+1)%2;
           
    }
        return ;
}
int main() 
{
      int t,i;
        char c;
    int a,b;
        scanf("%d",&t);
        while(t--)     
    {
         scanf("%d%d",&n,&m);
               init();
               getchar();
               for (i=1;i<=m;i++)         
        {
            scanf("%c %d %d",&c,&a,&b);
            getchar();
            if(c=='D') 
            {
                     join(a,b);
                   
            } else 
            {
                   if(find(a)!=find(b))       
                   printf("Not sure yet.n");      
                   else      
                   {   
                   if(r[a]==r[b])          
                   printf("In the same gang.n"); 
                   else          
                   printf("In different gangs.\n");  
                   }     
                   }   
                   }      
                   }   
                   return 0; 
                   }