卿学姐与诡异村庄

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
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

代码

 1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<algorithm> 5 #include<vector> 6 #include<queue> 7 const int MAXN=1000005; 8 using namespace std; 9 10 int vis[MAXN],N,next_[MAXN],think_huai[MAXN],col[MAXN];11 vector<int> 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 }

长长的可能会TLE的二分图

据说并查集是正解,类似食物链,待写~

cdoj 1328 卿学姐与诡异村庄 Label:并查集 || 二分图染色

声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉：投诉/举报工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。

联系
我们

首页 > 代码库 > cdoj 1328 卿学姐与诡异村庄 Label:并查集 || 二分图染色