hdu1811RankofTetris并查集+拓扑排序

/*
用并查集把成绩相等的人放在一起。
然后根据关系，把他们连起来。
然后拓扑排序。
如果拓扑排序结束之后，拓扑到的边数和输入的边数不同，那么肯定出现环了，那么就是信息错误。0
否则，如果某个时刻出现两个点的入度都为0，那么就出现信息不完整。
其他的就是结果正确了。
*/
#include
#include
#include
#include
using namespace std;
struct list
{
int u;
int v;
int next;
} edge[200000];
int head[20000];
int nums;
int ru[20000];
int chu[20000];
int f[20000];
int vis[20001];
void add(int u,int v)
{
ru[v]++;
chu[u]++;
edge[nums].u=u;
edge[nums].v=v;
edge[nums].next=head[u];
head[u]=nums++;
}
void init()
{
memset(head,-1,sizeof(head));
nums=0;
memset(ru,0,sizeof(ru));
memset(vis,0,sizeof(vis));
memset(chu,0,sizeof(chu));
}
int fx(int x)
{
while(x!=f[x])x=f[x];
return x;
}
int a[20000],b[20000];
char cp[20000];
int main()
{
int n,m,i;
while(~scanf("%d%d%*c",&n,&m))
{
init();
int bb;
bb=m;
for(i=0; i<=n; i++)f[i]=i;
for(i=1; i<=m; i++)
{
scanf("%d %c %d%*c",&a[i],&cp[i],&b[i]);
if(cp[i]==‘=‘)
{
f[fx(a[i])]=fx(b[i]);
bb--;
}
}
for(i=1; i<=m; i++)
{
int aa,bb;
aa=fx(a[i]);
bb=fx(b[i]);
if(cp[i]==‘<‘)add(aa,bb);
if(cp[i]==‘>‘)add(bb,aa);
}
int st=i;
int bian=0;
int leap=0;
int leap2=0;
while(1)
{
leap=0;
for(i=0; i {
if(f[i]==i&&ru[i]==0&&!vis[i])
{
leap++;
if(leap==1)
{
vis[i]=1;
st=i;
}
}
}
if(leap==0)break;
if(leap>1)leap2=1;
for(i=head[st]; i!=-1; i=edge[i].next)
{
int v=edge[i].v;
bian++;
ru[v]--;
}
}
if(bian!=bb)
{
cout<<"CONFLICT"< continue;
}
if(leap2)
{
cout<<"UNCERTAIN"< continue;
}
cout<<"OK"< }
return 0;
}

hdu-1811-Rank of Tetris-并查集+拓扑排序,布布扣,bubuko.com