卿学姐与诡异村庄

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

Submit  Status

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

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

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

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

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

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

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

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

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

Input

第一行一个整数 N N，表示村庄总共有 N N个人，村民从 1 1开始编号到 N N

1≤N≤100000 1≤N≤100000

接下来 N N行，每行两个整数， ai,t ai,t，如果 t t是 1 1，那么说明第 i i个人认为第 ai ai个人是好人。如果 t t是 2 2，那么说明第 i i个人认为第 ai ai个人是坏人。

1≤ai≤N 1≤ai≤N

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都是坏人，就能解释得通这些指控

Source

2016 UESTC Training for Data Structures

题解：并查集经典应用——判断矛盾，每个人的说真话与说假话分别为一个点，然后对于并存状态连边，当说真话与说假话同时存在的时候即为矛盾

代码如下：

#include <iostream> #include <cstdio> const int maxn=100000; using namespace std; int par[5*maxn]; void init(int n){ for (int i = 0;i<n;i++) { par[i] = i; } } int Find(int x){ if(par[x] != x){ par[x] = Find(par[x]); return par[x]; } } bool same(int x,int y){ return Find(x) == Find(y); } int main() { int N,a,b,k=0; scanf("%d",&N); init(2*N); for(int i = 0;i<N;i++) { scanf("%d %d",&a,&b); if(b==1) { par[i]=Find(par[a-1]); par[i+N]=Find(par[N+a-1]); } else { par[i]=Find(par[a+N-1]); par[N+i]=Find(par[a-1]); } } for(k=0;k<N;k++) { if(same(k,N+k)){ printf("One face meng bi"); break; } } if(k==N) printf("Time to show my power"); return 0; }