又是一年CET46(0243)
问题描述
CET46 成绩出来啦，一群学生在谈论他们的成绩。A说他的成绩比B高，B说他的成绩比C低，D说他的成绩和E一样……
他们当中可能有人在说谎。你的任务就是判断是否有人在说谎。
PS：
A < B 表示A的成绩比B低。
A > B 表示A的成绩比B高。
A = B 表示A的成绩和B一样。
输入
有多组数据。对于每组数据
第一行两个整数 N和M,分别代表有N个学生(编号1—N)，和已知的M个关系。（1 < N <= 200 ，0 < M < 40000）
第二到第M+1行，每行对应一个关系。
输出
如果有人说谎输出 “Someone have told lies!”，否则输出 “Maybe they are all honest!”。
样例输入
4 3
1 < 2
1 < 3
2 > 3
3 3
1 > 2
2 > 3
3 = 1
样例输出
Maybe they are all honest!
Someone have told lies!
由于‘=’的存在，因此先用并查集合并。
额、可能想复杂了，应该有其他简单的方法。
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
#define INF 0x3f3f3f3f
#define N 210
#define M 200200 struct les{
int a,b;
}p[M];
int tot;
int n,m;
int flag;
int f[N];
int in[N];
int vis[N];
int mpt[N][N]; void init()
{
tot=;
flag=;
for(int i=;i<=n;i++) f[i]=i;
}
int Find(int x)
{
if(x!=f[x]) f[x]=Find(f[x]);
return f[x];
}
void UN(int x,int y)
{
x=Find(x);
y=Find(y);
f[x]=y;
}
bool solve()
{
//build
int tn=;
memset(in,,sizeof(in));
memset(vis,,sizeof(vis));
memset(mpt,,sizeof(mpt));
for(int i=;i<=tot;i++){
int a=Find(p[i].a);
int b=Find(p[i].b);
if(!vis[a]) vis[a]=,tn++;
if(!vis[b]) vis[b]=,tn++;
if(!mpt[a][b]){ //重边判断
mpt[a][b]=;
in[b]++;
}
}
//work
priority_queue<int,vector<int>,greater<int> >q;
for(int i=;i<=n;i++){
if(!in[i] && vis[i]) q.push(i);
}
int cnt=;
while(!q.empty()){
int u=q.top();
q.pop();
cnt++;
for(int v=;v<=n;v++){
if(mpt[u][v] && vis[v]){
in[v]--;
if(!in[v]) q.push(v);
}
}
}
if(cnt<tn) return ;
return ;
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
init();
while(m--){
int a,b;
char c;
scanf(" %d %c %d",&a,&c,&b);
if(!flag) continue;
if(c!='='){
if(Find(a)==Find(b)) flag=;
if(c=='>') swap(a,b);
p[++tot].a=a;
p[tot].b=b;
}
else{
UN(a,b);
}
}
if(flag){
flag=solve();
if(flag) printf("Maybe they are all honest!\n");
else printf("Someone have told lies!\n");
}
else
printf("Someone have told lies!\n");
}
return ;
}