uestc08暑假集训1.数据结构解题报告poj

1、POJ 1703Find them, Catch themTime Limit: 1000MSMemory Limit: 10000KTotal Submissions: 5084Accepted: 1366DescriptionThe 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 i

2、dentify 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 = 105) criminals are currently in InputThe first line of t

3、he 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. OutputFor each message A a b in each case, your program should give the j

4、udgment based on the information got before. The answers might be one of In the same gang., In different gangs. and Not sure yet.Sample Input15 5A 1 2D 1 2A 1 2D 2 4A 1 4Sample OutputNot sure yet.In different gangs.In the same gang.题意：有两个命令，“D x y”，“A x y”命令。“D”命令表示 x y 元素属于不同的集合。“A”命令表示询问x y 元素是否是在

5、同一个集合里面。如果不是输出 In different gangs，是输出In the same gang. 如果不能确定，输出In different gangs.分析：此题和a bugs life 基本一样，均属于考察并查集应用的题目。因为题目中还需要记录一个集合的对立集合，所以还需要每个集合加一个peiou ，记录每个集合的对立集合。在合并集合的时候要注意，设命令为d a b ，a集合的代表元素为aa,b集合的代表元素为bb,aa的对立集合为peiouaa,b的对立集合peioubb.如果 peiouaa=0 表示 aa没有对立集合，核心代码如下： if(peiouaa&peioubb) unionset(aa,peioubb); unionset(bb,peiouaa); if(!peiouaa&!peioubb) peiouaa=