uestc08暑假集訓(xùn)1.數(shù)據(jù)結(jié)構(gòu)解題報(bào)告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.題意：有兩個(gè)命令，“D x y”，“A x y”命令?！癉”命令表示 x y 元素屬于不同的集合?！癆”命令表示詢問x y 元素是否是在

5、同一個(gè)集合里面。如果不是輸出 In different gangs，是輸出In the same gang. 如果不能確定，輸出In different gangs.分析：此題和a bugs life 基本一樣，均屬于考察并查集應(yīng)用的題目。因?yàn)轭}目中還需要記錄一個(gè)集合的對(duì)立集合，所以還需要每個(gè)集合加一個(gè)peiou ，記錄每個(gè)集合的對(duì)立集合。在合并集合的時(shí)候要注意，設(shè)命令為d a b ，a集合的代表元素為aa,b集合的代表元素為bb,aa的對(duì)立集合為peiouaa,b的對(duì)立集合peioubb.如果 peiouaa=0 表示 aa沒有對(duì)立集合，核心代碼如下： if(peiouaa&peioubb) unionset(aa,peioubb); unionset(bb,peiouaa); if(!peiouaa&!peioubb) peiouaa=