Codeforces Round #541 (Div. 2), problem: (D) Gourmet choice / codeforces 1131D

TAG 2000分我觉得虚高了。。

这题跟F感觉是一样的题啊，做法、思想都基本一样。

给出关系，让你给他们编号

由于有等于号，我们就用并查集，把相等的菜肴全部归到一道菜上，再根据<关系建图，因为从小到大编号比较方便，不用跑最长路，所以依据<关系建图。

那么No的情况呢？No的情况就是图里面有环，或者该点（根结点）不在图上。

我们利用拓扑排序，每次给入度为0的点编号，从而实现题目的要求

大概长这个样子

#include<bits/stdc++.h>
using namespace std;
struct edge
{
    int v,val,next;
    edge(int v,int next):v(v),next(next){};
    edge(){};
}e[1000005];
int tot,head[2005],idg[2005],ans[2005];
bool vis[2005];
char s[1005][1005];
int n,m,num;
void init()
{
    tot=0,num=1;
    memset(head,-1,sizeof head);
    memset(vis,false,sizeof vis);
    memset(idg,0,sizeof idg);
}
int pa[2005];
int findset(int x){ return pa[x]!=x?pa[x]=findset(pa[x]):x;}
void combine(int x,int y)
{
    int u=findset(x),v=findset(y);
    if(u!=v)
        pa[v]=u;
}
void addedge(int u,int v)
{
    e[tot]=edge(v,head[u]);
    idg[v]++;
    head[u]=tot++;
}
queue<int>q;
void toposort()
{
    for(int i=1;i<=n+m;i++) // num是编号
        if(idg[findset(i)]==0) //因为非根结点是没有算在图内的，而是依附于根结点
        q.push(i),ans[i]=num;
        num++;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=head[u];~i;i=e[i].next)
        {
            int v=e[i].v;
            idg[v]--;
            if(idg[v]==0)
                q.push(v),ans[v]=num,vis[num]=true;
        }
        if(vis[num]) //代表我们的num已经编过号了，同一编号的点已经遍完了
        num++;
    }
}

int main()
{
    int i,j,k,sum;
    while(~scanf("%d%d",&n,&m))
    {
        init();
        for(i=1;i<=n+m;i++)
            pa[i]=i;
        for(i=1;i<=n;i++)
        {
            scanf("%s",s[i]+1);
        }
        for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
        {
            if(s[i][j]=='=')
                combine(i,j+n);
        }
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=m;j++)
            {
                if(s[i][j]=='<')
                {
                    int u=findset(i),v=findset(n+j); //用根结点建图
                    if(v==u)
                    {
                        printf("NO\n");
                        return 0;
                    }
                    addedge(u,v);
                }

                else if(s[i][j]=='>')
                {
                    int u=findset(i),v=findset(n+j); //用根结点建图
                    if(v==u)
                    {
                        printf("NO\n");
                        return 0;
                    }
                    addedge(v,u);
                }
            }
        }
        toposort();
        for(i=1;i<=n+m;i++)
        {
            if(ans[i]==0)
            {
                if(ans[findset(i)]==0)
                {
                    printf("No\n");
                    return 0;
                }
                else
                    ans[i]=ans[findset(i)];
            }
        }
        printf("Yes\n");
        for(i=1;i<=n;i++)
            printf(i==n?"%d\n":"%d ",ans[i]);
        for(i=n+1;i<=n+m;i++)
            printf(i==n+m?"%d\n":"%d ",ans[i]);

    }
    return 0;
}

。