卿学姐与诡异村庄
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≤N
Output
如果存在一个好人坏人的分类能够满足所有的指控，那么输出"Time to show my power"，否则输出"One face meng bi"
Sample input and output
| Sample Input | Sample Output |
|---|---|
32 23 11 2 | Time to show my power |
32 23 21 2 | One face meng bi |
Hint
第一组样例中，如果1是好人，2和3都是坏人，就能解释得通这些指控
Source
2016 UESTC Training for Data Structures
代码
长长的可能会TLE的二分图1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 const int MAXN=1000005; 8 using namespace std; 9 10 int vis[MAXN],N,next_[MAXN],think_huai[MAXN],col[MAXN];11 vector vec;12 //1(2-1)是坏人,0是好人 13 int dfs(int x){14 vis[x]=1;15 if( next_[x] && !vis[next_[x] ] ) dfs( next_[x] );16 vec.push_back(x);17 }18 19 int paint(int x,int c){20 vis[x]=1;//不管怎样都已经访问 ,但col不一样 21 col[x]=c; //之后染色成功才会进行染色22 23 if(next_[x]){24 if(c){ //如果x是坏人,染反色 25 if(col[next_[x]]>=0){ //如果儿纸已经染色 26 if( (think_huai[x]^1) != col[next_[x]] ) {col[x]=-1;return 0;}//儿纸不成功就不染 27 }28 else if(!paint(next_[x],think_huai[x]^1)) {col[x]=-1;return 0;}29 }30 else{31 if(col[next_[x]]>=0){32 if( (think_huai[x]) != col[next_[x]] ) {col[x]=-1;return 0;}33 }34 else if(!paint(next_[x],think_huai[x])) {col[x]=-1;return 0;}35 }36 }37 38 return 1;39 }40 41 int scc(){42 memset(vis,0,sizeof(vis));43 for(int i=1;i<=N;i++)44 if(!vis[i]) dfs(i);45 46 memset(vis,0,sizeof(vis));47 for(int i=N-1;i>=0;i--){48 int now=vec[i];49 if(!vis[now]){50 if(!paint(now,1)){51 if(!paint(now,0)){52 puts("One face meng bi");53 exit(0);54 }55 }56 }57 }58 // paint(1,1);59 return 1;60 }61 62 int main(){63 // freopen("01.in","r",stdin);64 scanf("%d",&N);65 for(int i=1;i<=N;i++){66 int flag=0,tmp=0;67 scanf("%d%d",&tmp,&flag);68 next_[i]=tmp;think_huai[i]=flag-1;69 }70 71 memset(col,-1,sizeof(col));72 if(scc()) puts("Time to show my power");73 return 0;74 } 据说并查集是正解,类似食物链,待写~
长长的速度没差多少的并查集1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 const int MAXN=100005; 8 using namespace std; 9 10 int N;11 int think_list[MAXN],think_label[MAXN],vis[MAXN];12 int fa[2*MAXN],d[MAXN];13 //fa 前一半是好人 后一半是坏人 14 15 int Find(int a){16 if(a==fa[a]) return a;17 else return fa[a]=Find(fa[a]);18 }19 20 void unite(int a,int b){21 int ta=Find(a),tb=Find(b);22 if(ta!=tb) fa[ta]=tb;23 }24 25 int check(int x,int c){26 d[x]=c;27 vis[x]=1;28 if(think_list[x]){29 int to=think_list[x],flag=think_label[x];30 if(!c){ //如果c是好人 31 if(vis[to]){32 if(Find(x)==Find(to+MAXN)&&flag==d[to]^1) {vis[x]=0;return 0;}33 if(Find(x)==Find(to)&&flag==d[to]^1) {vis[x]=0;return 0;}34 }35 if(!vis[to]&&!check(to,flag)) {vis[x]=0;return 0;} 36 }37 else{38 if(vis[to]){39 if(Find(x)==Find(to+MAXN)&&flag==d[to]) {vis[x]=0;return 0;}40 if(Find(x)==Find(to)&&flag==d[to]) {vis[x]=0;return 0;}41 }42 if(!vis[to]&&!check(to,flag^1)) {vis[x]=0;return 0;} 43 }44 }45 return 1;46 }47 48 int main(){49 // freopen("01.in","r",stdin);50 memset(d,-1,sizeof(d));51 52 scanf("%d",&N);53 for(int i=1;i<2*MAXN;i++) fa[i]=i;54 55 for(int i=1;i<=N;i++){56 int flag,x;57 scanf("%d%d",&x,&flag);flag-=1;58 think_list[i]=x;59 think_label[i]=flag;//1是坏人 0是好人 60 61 if(flag==0){62 unite(i,x);63 // unite(i+MAXN,x);64 }65 else{ //坏人 66 unite(i,x+MAXN);67 // unite(i+MAXN,x+MAXN);68 }69 }70 for(int i=1;i<=N;i++){71 if(!vis[i]){72 if(!check(i,0)){73 if(!check(i,1)){74 puts("One face meng bi");75 exit(0);76 }77 }78 }79 }80 puts("Time to show my power");81 return 0;82 }