卿学姐与诡异村庄

Time Limit: 4500/1500MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others)

日复一日，年复一年，春去秋来。

卿学姐终于从天行廖那里毕业啦。出山的卿学姐首先来到了一个诡异的村庄。

在这个村庄中，只有两种人，一种是好人，一种是坏人。

好人只说真话，坏人只说假话。

村庄虚伪的平静由于卿学姐的到来，终于被打破了。

人们开始互相指控，每个人都会说另外一个人是否是好人。

卿学姐修行途中只学会了膜法，却不谙世事，所以卿学姐无法确认哪些人是好人，哪些人是坏人。

但是机智的卿学姐意识到可以通过这些人的指控来分辨。

现在告诉你村庄中每个人指控谁是否为好人，请问是否有个合理的分类能够符合所有的指控。

Input

第一行一个整数

接下来

Output

如果存在一个好人坏人的分类能够满足所有的指控，那么输出"Time to show my power"，否则输出"One face meng bi"

Sample input and output

Sample Input	Sample Output
3 2 2 3 1 1 2	Time to show my power
3 2 2 3 2 1 2	One face meng bi

Hint

第一组样例中，如果1是好人，2和3都是坏人，就能解释得通这些指控

思路：

听郭大侠讲了题解后才会做的，原来查并集也能这么用，惊讶！

– 思路就是令A是好人表示为Ag，A是坏人表示为Ab。

– 如果A说B是坏人，那么将Ag和Bb合并，将Ab和Bg合并。

– 如果A说B是好人，那么将Ag和Bg合并，将Ab和Bb合并。

– 如果最后Ag和Ab在同一个集合，就无解。

好人我用的是前1e5个数代表，坏人的话直接映射到1e5之后。

如果在集合中就用1代表，反之用0代表

然后处理完所有的询问之后，把集合中的所有数扫一遍判断是否存在非法的数据（一开始我只用集合中是否同时存在第一个人是好人也是坏人来判断，然后果断wa了，，，）

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <cstdio>
 4 #include <cmath>
 5 #include <cstring>
 6 #include <queue>
 7 #include <stack>
 8 #include <map>
 9 #include <vector>
10 #include <cstdlib>
11 #include <string>
12 
13 #define PI acos((double)-1)
14 #define E exp(double(1))
15 using namespace std;
16 const int has=1e5;
17 int root[2*has+10];
18 int fd(int x)
19 {
20     return x!=root[x]?root[x]=fd(root[x]):x;
21 }
22 void join(int x,int y)
23 {
24     int a=fd(x),b=fd(y);
25     if(a!=b)root[a]=b;
26 }
27 int main (void)
28 {
29     int n;
30     cin>>n;
31     for(int i=1;i<=has*2+9;i++)
32         root[i]=i;
33     for(int i=1;i<=n;i++)
34     {
35         int x,op;
36         scanf("%d%d",&x,&op);
37         if(op==1)
38             join(i,x),join(has+i,has+x);
39         else
40             join(i,has+x),join(has+i,x);
41 
42     }
43     for(int j=1;j<=n;j++)
44             if(fd(j)==fd(has+j))
45             {
46                 printf("One face meng bi
");return 0;
47             }
48     printf("Time to show my power
");
49     return 0;
50 }

View Code