首页 > 代码库 > hdu1811 Rank of Tetris

hdu1811 Rank of Tetris

2024-07-19 00:30:42   219人阅读

 　　这道题是拓扑排序和并查集的综合运用。

　　由于排行榜是一种从高到低的排序。所以在拓扑排序的时候，如果有一次加入的入度为零的点数大于1，就有变得不确定了（UNCERTAIN）。

　　由于只有一棵树，当树的数量大于1，就矛盾。还有一种产生矛盾的可能是，当输入的是a>b(或者a<b)时，但是并查集中他们的父节点相同。因为这题的一个集合其实被当成了一个点。这样不相等的相等就是矛盾的。

#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int N = 10010, M =20010;struct node{    int to, next;};node edge[M];int ind[N], head[N],que[N],f[N],L[N],R[N];int iq,tot,num,FLAG;char ch[N];int Find(int x){    if(x==f[x]) return x;    return f[x]=Find(f[x]);}void topo(int n){    int i,k,j=0,s;    for(i=0;i<n;i++)        if(ind[i]==0&&i==Find(i)) que[j++]=i;    FLAG=0;    if(j>1) FLAG=1;    s=j;    for(i=0;i<j;i++)    {        if(j-s>1) FLAG=1;        s=j;        int u=que[i];        num--;        for(k=head[u]; k!=-1; k=edge[k].next)        {            ind[edge[k].to]--;            if(ind[edge[k].to]==0)                que[j++]=edge[k].to;        }    }    iq=j;}void addedge(int i,int j){    edge[tot].to=j;edge[tot].next=head[i];head[i]=tot++;}void Link(int i,int j){    int a=Find(i),b=Find(j);    if(a!=b) {f[b]=a;}}void init(){    tot=0;    for(int i=0;i<N;i++)    {        f[i]=i;        head[i]=-1;        ind[i]=0;    }}int main(){    //freopen("test.txt","r",stdin);    int n,m,i,j,k;    while(scanf("%d%d",&n,&m)!=EOF)    {        init();        int flag=1;        num=n;        for(i=0;i<m;i++)        {            scanf("%d %c %d",&L[i],&ch[i],&R[i]);            if(ch[i]==‘=‘) {Link(L[i],R[i]);num--;}        }        for(i=0;i<m;i++)        {            if(ch[i]==‘=‘) continue;            int a=Find(L[i]),b=Find(R[i]);            if(a==b) flag=0;            if(ch[i]==‘>‘) {addedge(a,b); ind[b]++;}            else {addedge(b,a); ind[a]++;}        }        topo(n);        if(num>1||!flag) printf("CONFLICT\n");        else if(FLAG) printf("UNCERTAIN\n");        else printf("OK\n");    }    return 0;}

 

hdu1811 Rank of Tetris


联系
我们