卿学姐与诡异村庄
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 |
|---|---|
3 |
Time to show my power |
3 |
One face meng bi |
Hint
第一组样例中，如果1是好人，2和3都是坏人，就能解释得通这些指控
Source
2016 UESTC Training for Data Structures
代码
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
const int MAXN=;
using namespace std; int vis[MAXN],N,next_[MAXN],think_huai[MAXN],col[MAXN];
vector<int> vec;
//1(2-1)是坏人,0是好人
int dfs(int x){
vis[x]=;
if( next_[x] && !vis[next_[x] ] ) dfs( next_[x] );
vec.push_back(x);
} int paint(int x,int c){
vis[x]=;//不管怎样都已经访问 ,但col不一样
col[x]=c; //之后染色成功才会进行染色 if(next_[x]){
if(c){//如果x是坏人,染反色
if(col[next_[x]]>=){//如果儿纸已经染色
if( (think_huai[x]^) != col[next_[x]] ) {col[x]=-;return ;}//儿纸不成功就不染
}
else if(!paint(next_[x],think_huai[x]^)) {col[x]=-;return ;}
}
else{
if(col[next_[x]]>=){
if( (think_huai[x]) != col[next_[x]] ) {col[x]=-;return ;}
}
else if(!paint(next_[x],think_huai[x])) {col[x]=-;return ;}
}
} return ;
} int scc(){
memset(vis,,sizeof(vis));
for(int i=;i<=N;i++)
if(!vis[i]) dfs(i); memset(vis,,sizeof(vis));
for(int i=N-;i>=;i--){
int now=vec[i];
if(!vis[now]){
if(!paint(now,)){
if(!paint(now,)){
puts("One face meng bi");
exit();
}
}
}
}
// paint(1,1);
return ;
} int main(){
// freopen("01.in","r",stdin);
scanf("%d",&N);
for(int i=;i<=N;i++){
int flag=,tmp=;
scanf("%d%d",&tmp,&flag);
next_[i]=tmp;think_huai[i]=flag-;
} memset(col,-,sizeof(col));
if(scc()) puts("Time to show my power");
return ;
}长长的可能会TLE的二分图
据说并查集是正解,类似食物链,待写~
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
const int MAXN=;
using namespace std; int N;
int think_list[MAXN],think_label[MAXN],vis[MAXN];
int fa[*MAXN],d[MAXN];
//fa 前一半是好人 后一半是坏人 int Find(int a){
if(a==fa[a]) return a;
else return fa[a]=Find(fa[a]);
} void unite(int a,int b){
int ta=Find(a),tb=Find(b);
if(ta!=tb) fa[ta]=tb;
} int check(int x,int c){
d[x]=c;
vis[x]=;
if(think_list[x]){
int to=think_list[x],flag=think_label[x];
if(!c){//如果c是好人
if(vis[to]){
if(Find(x)==Find(to+MAXN)&&flag==d[to]^) {vis[x]=;return ;}
if(Find(x)==Find(to)&&flag==d[to]^) {vis[x]=;return ;}
}
if(!vis[to]&&!check(to,flag)) {vis[x]=;return ;}
}
else{
if(vis[to]){
if(Find(x)==Find(to+MAXN)&&flag==d[to]) {vis[x]=;return ;}
if(Find(x)==Find(to)&&flag==d[to]) {vis[x]=;return ;}
}
if(!vis[to]&&!check(to,flag^)) {vis[x]=;return ;}
}
}
return ;
} int main(){
// freopen("01.in","r",stdin);
memset(d,-,sizeof(d)); scanf("%d",&N);
for(int i=;i<*MAXN;i++) fa[i]=i; for(int i=;i<=N;i++){
int flag,x;
scanf("%d%d",&x,&flag);flag-=;
think_list[i]=x;
think_label[i]=flag;//1是坏人 0是好人 if(flag==){
unite(i,x);
// unite(i+MAXN,x);
}
else{//坏人
unite(i,x+MAXN);
// unite(i+MAXN,x+MAXN);
}
}
for(int i=;i<=N;i++){
if(!vis[i]){
if(!check(i,)){
if(!check(i,)){
puts("One face meng bi");
exit();
}
}
}
}
puts("Time to show my power");
return ;
}长长的速度没差多少的并查集