首页 > 代码库 > Hiho----无间道之并查集

Hiho----无间道之并查集

2024-11-19 07:21:39   202人阅读

题目：

时间限制:20000ms
单点时限:1000ms
内存限制:256MB

描述

这天天气晴朗、阳光明媚、鸟语花香，空气中弥漫着春天的气息……额，说远了，总之，小Hi和小Ho决定趁着这朗朗春光出去玩。

但是刚刚离开居住的宾馆不久，抄近道不小心走入了一条偏僻小道的小Hi和小Ho就发现自己的前方走来了几个彪形大汉，定睛一看还都是地地道道的黑人兄弟！小Hi和小Ho这下就慌了神，捡肥皂事小，这一身百把来斤别一不小心葬身他乡可就没处说去了。

就在两人正举足无措之时，为首的黑叔叔从怀里掏出了一件东西——两张花花绿绿的纸，分别递给了小Hi和小Ho。

小Hi和小Ho接过来，只见上面写道（译为中文）：“本地最大的帮派——青龙帮，诚邀您的加入！”下面还详细的列出了加入青龙帮的种种好处。

于是两人略感心安，在同黑叔叔们交谈一番之后，已是均感相见恨晚。同时，在小Hi和小Ho表示自己不日便将回国之后，黑叔叔们也没有再提加入帮派之事，但是那为首的黑叔叔思索一会，开口道（译为中文）：“我现在有一个难题，思索了很久也没法子解决，既然你们俩都是高材生，不如来帮我看看。”

小Hi和小Ho点了点头表示没问题，于是黑叔叔继续说道：“这个问题是这样的，我们帮派最近混进了许多警察的卧底，但是在我们的调查过程中只能够知道诸如‘某人和另一个人是同阵营的’这样的信息，虽然没有办法知道他们具体是哪个阵营的，但是这样的信息也是很重要的，因为我们经常会想要知道某两个人究竟是不是同一阵营的。”

小Hi和小Ho赞同的点了点头，毕竟无间道也都是他们看过的。

黑叔叔接着说道：“于是现在问题就来了，我希望你们能写出这样一个程序，我会有两种操作，一种是告诉它哪两个人是同一阵营的，而另一种是询问某两个人是不是同一阵营的……既然你们就要回国了，不如现在就去我们帮派的总部写好这个程序再走把。”

为了生命安全与……小Hi和小Ho都不得不解决这个问题！那么他们究竟从何下手呢？

提示：说起来其实就是不断的合并集合嘛~

输入

每个测试点（输入文件）有且仅有一组测试数据。

每组测试数据的第1行为一个整数N，表示黑叔叔总共进行的操作次数。

每组测试数据的第2~N+1行，每行分别描述黑叔叔的一次操作，其中第i+1行为一个整数op_i和两个由大小写字母组成的字符串Name1_i, Name2_i，其中op_i只可能为0或1，当op_i=0时，表示黑叔叔判定Name1_i和Name2_i是同一阵营的，当op_i=1时，表示黑叔叔希望知道Name1_i和Name2_i是否为同一阵营的。

对于100%的数据，满足N<=10^5, 且数据中所有涉及的人物中不存在两个名字相同的人（即姓名唯一的确定了一个人），对于所有的i，满足Name1_i和Name2_i是不同的两个人。

输出

对于每组测试数据，对于黑叔叔每次op_i=1的操作，输出一行，表示查询的结果：如果根据已知信息（即这次操作之前的所有op_i=0的操作），可以判定询问中的两个人是同一阵营的，则输出yes，否则输出no。

样例输入
100 Steven David0 Lcch Dzx1 Lcch Dzx1 David Dzx0 Lcch David0 Frank Dzx1 Steven Dzx1 Frank David0 Steven Dzx0 Dzx Frank
样例输出
yesnoyesyes

 

算法分析：

          首先，名字标记，对名词按照出现的顺序赋予顺序值（从1开始）。

          名字识别借鉴了

                       Hiho中的十佳代码 后面会一并贴出

                       作者：ㄟ别栖息寒枝上，别独自饮伤ㄏ 

          如果为0操作且两者均为第一次出现，则赋予两者类别号，即两者顺序值得最小值。

          如果为0操作且两者有一人已有类别号，则将其值赋给另一者的类别号(大于0)。

          如果为0操作且两者均有类别号，则遍历类别号数组，将两种类型合并，类别号为两者类别号的最小值。

          如果为1操作，且两者类别号相同，则输出yes;

          为1操作时，如果两者类别号相同且不为0，则输出yes；否则输出no.

           

 我的代码：
 1 import java.util.Scanner; 2  3  4  5  6 public class Main { 7     public static int c=0; 8     public static int[] e = new int[100100]; 9     public static int[][] j= new int[100100][52];10     public static int d=0;11     public static int add(){12         c++;        13         return c;14     }15     public static int find(char[] k,int[][] j){16         int p=0,t;17         for(int i=0; i<k.length; i++){18             t=k[i]>‘Z‘?k[i]-‘a‘+26:k[i]-‘A‘;19             if(j[p][t]==0)j[p][t]=add();20             p=j[p][t];21             22         }23         if(e[p]==0){24             e[p]=++d;25             return e[p];26         }27         else28             return e[p];    29     }30     public static void main(String[] argv){31         int [] x = new int [10010];32         Scanner in = new Scanner(System.in);33         int num =Integer.parseInt(in.nextLine());34         int max=0;35         String out ="";36         for(int i=0; i<num; i++){37             String[] s = in.nextLine().split(" ");38             int o = Integer.parseInt(s[0]);39             int A = find(s[1].toCharArray(), j);40             int B = find(s[2].toCharArray(), j);    41             if(A>max)42                 max=A;43             if(B>max)44                 max=B;45             int min = A<B? A:B;46 47             if(o==0)48             {49                 if(x[A]==0&&x[B]==0)50                     {51                      x[A]=min; x[B]=min;                52                     }53                 else{54                     if(x[A]!=0&&x[B]!=0){55                         min=x[A]<x[B]? x[A]:x[B];56                         int tmp=x[A]+x[B]-min;57                         for(int w=1; w<=max; w++){58                             if(x[w]==tmp)59                                 x[w]=min;60                         }61                     }62                     else{63                         if(x[A]==0)64                             x[A]=x[B];65                         else66                             x[B]=x[A];67                     }68                 }69             }70             if(o==1){71                 if(x[A]==x[B]){72                     if(x[A]==0)73                         out=out+"no ";74                     else75                         out=out+"yes ";76                 }        77                 else78                     out=out+"no ";79             }80             81         }82         in.close();83         out=out+"end";84         String[] OUT = out.split(" ");85         for(int t=0; t<OUT.length-1; t++){    86             System.out.println(OUT[t]);87         }88     89     }90 91 }

大神代码：

 1 #include <cstdio> 2 #include <cstring> 3 const int N=100010; 4 #define C(c) c>‘Z‘?c-‘a‘+26:c-‘A‘ 5 int e[N],x[N][26*2],c=0,d=0; 6 int add(){ 7     ++c; 8     e[c]=0; 9     memset(x[c],0,sizeof(x[c]));10     return c;11 }12 int find(char*s){13     int p=0,t;14     while(*s){15         t=C(*s);16         if(!x[p][t])x[p][t]=add();17         p=x[p][t];18         ++s;19     }20     return e[p]?e[p]:e[p]=++d;21 }22 char a[100],b[100];23 int r[N],n,o,A,B;24 int find(int i){return i==r[i]?i:r[i]=find(r[i]);}25 int main(){26     for(scanf("%d",&n);n--;){27         scanf("%d%s%s",&o,a,b);28         A=find(a);B=find(b);29         if(!r[A])r[A]=A;30         if(!r[B])r[B]=B;31         A=find(A);B=find(B);32         if(o)puts(A==B?"yes":"no");33         else r[A]=B;34     }35     return 0;36 }

Hiho----无间道之并查集


联系
我们