卿学姐与诡异村庄
Time Limit: 4500/1500MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others)
Submit Status
日复一日，年复一年，春去秋来。
卿学姐终于从天行廖那里毕业啦。出山的卿学姐首先来到了一个诡异的村庄。
在这个村庄中，只有两种人，一种是好人，一种是坏人。
好人只说真话，坏人只说假话。
村庄虚伪的平静由于卿学姐的到来，终于被打破了。
人们开始互相指控，每个人都会说另外一个人是否是好人。
卿学姐修行途中只学会了膜法，却不谙世事，所以卿学姐无法确认哪些人是好人，哪些人是坏人。
但是机智的卿学姐意识到可以通过这些人的指控来分辨。
现在告诉你村庄中每个人指控谁是否为好人，请问是否有个合理的分类能够符合所有的指控。
Input
第一行一个整数NN，表示村庄总共有NN个人，村民从11开始编号到NN
1≤N≤1000001≤N≤100000
接下来NN行，每行两个整数，ai,tai,t，如果tt是11，那么说明第ii个人认为第aiai个人是好人。如果tt是22，那么说明第ii个人认为第aiai个人是坏人。
1≤ai≤N1≤ai≤N
Output
如果存在一个好人坏人的分类能够满足所有的指控，那么输出"Time to show my power"，否则输出"One face meng bi"
Sample input and output
3 | Time to show my power |
3 | One face meng bi |
Hint
第一组样例中，如果1是好人，2和3都是坏人，就能解释得通这些指控
这道题以前做过一次类似的，结果这一次又是One face meng bi。。。。。。。。。。。。。。。。。。
#include<iostream>
#include<cstring>
#include<cstdio> using namespace std;
const int N = + ;
int pre[N << ]; void Init(){
for(int i = ; i < N * ; i++) pre[i] = i;
} int Find(int x){
return pre[x] == x ? x : (pre[x] = Find(pre[x]));
} void Merge(int x, int y){
x = Find(x), y = Find(y);
if(x != y) pre[y] = x;
} int Good(int x){
return x;
} int Bad(int x){
return N + x;
} bool Same(int x, int y){
return Find(x) == Find(y);
} int main(){
int n, x, p;
scanf("%d", &n);
Init();
for(int i = ; i <= n; i++){
scanf("%d %d", &x, &p);
if(p == ){
Merge(Good(i), Good(x));
Merge(Bad(i), Bad(x));
}else{
Merge(Good(i), Bad(x));
Merge(Bad(i), Good(x));
}
}
for(int i = ; i <= n; i++){
if(Same(Good(i), Bad(i))){
printf("One face meng bi\n");
return ;
}
}
printf("Time to show my power\n");
return ;
}