首页 > 代码库 > HDU 1811

HDU 1811

2024-08-04 18:50:59   219人阅读

http://acm.hdu.edu.cn/showproblem.php?pid=1811

中文码题

对于等号的情况，用并查集合并（因为编号不同一定可以分出先后）

然后判断能否构成拓扑排序，以及拓扑排序是不是唯一的

题不难，考验代码能力，能1A证明手感还不错

#include <iostream>#include <cstdio>#include <cstring>#include <map>#include <algorithm>#include <queue>#include <cmath>#include <stack>#include <set>using namespace std;int vis[10005],head[10005],cnt,fa[10005],st[10005];struct p{    int a,b;    char op[5];}kk[10005];struct node{    int s,t,nxt;}e[1000005];void add(int s,int t){    e[cnt].s=s;e[cnt].t=t;e[cnt].nxt=head[s];head[s]=cnt++;}void INIT(){    cnt=0;    memset(head,-1,sizeof(head));}int find(int x){    return fa[x]==x?x:fa[x]=find(fa[x]);}int dfs(int u){    vis[u]=-1;    for(int i=head[u];i!=-1;i=e[i].nxt){        int v=e[i].t;        if(vis[v]<0)return 0;        else if(!vis[v] && !dfs(v))return 0;    }    vis[u]=1;    return 1;}int OK(int n){    for(int i=0;i<n;i++){        if(!vis[i] && !st[i] && !dfs(i))return 0;    }    return 1;}int IN[10005];int main(){    int n,m;    while(~scanf("%d%d",&n,&m)){        INIT();        for(int i=0;i<n;i++)fa[i]=i;        memset(IN,0,sizeof(IN));        memset(st,0,sizeof(st));        int flag=1;        for(int i=0;i<m;i++){            scanf("%d%s%d",&kk[i].a,kk[i].op,&kk[i].b);            if(kk[i].op[0]==‘=‘){                int pa=find(kk[i].a);                int pb=find(kk[i].b);                if(pa!=pb){                    fa[pa]=pb;                    st[pa]=1;                }            }            else{                int pa=find(kk[i].a);                int pb=find(kk[i].b);                    if(pa==pb)flag=0;            }        }        if(!flag)puts("CONFLICT");//所给信息矛盾         else{            for(int i=0;i<m;i++){                if(kk[i].op[0]==‘>‘){                    add(find(kk[i].a),find(kk[i].b));                    IN[find(kk[i].b)]++;                }                else if(kk[i].op[0]==‘<‘){                    add(find(kk[i].b),find(kk[i].a));                    IN[find(kk[i].a)]++;                }            }            memset(vis,0,sizeof(vis));            if(!OK(n))puts("CONFLICT");//有环             else{                queue <int> q;                for(int i=0;i<n;i++){                    if(!st[i] && !IN[i])                        q.push(i);                }                int flag=1;                while(!q.empty()){                    if(q.size()>1){                        flag=0;                        break;                    }                    int u=q.front();                    q.pop();                    for(int i=head[u];i!=-1;i=e[i].nxt){                        int v=e[i].t;                        IN[v]--;                        if(!IN[v])q.push(v);                    }                }                if(!flag)puts("UNCERTAIN");//拓扑结构一层多于一个点，有多种情况                 else puts("OK");            }        }    }    return 0;}
View Code

 

HDU 1811


联系
我们