Codeforces Round #541 (Div. 2)D（并查集（dsu），拓扑排序）

#include<bits/stdc++.h>
using namespace std;
vector<int>g[2007];
int fa[2007],vis[2007],num[2007];
char s[2007][2007];
int find_(int x){
    if(fa[x]==x)
        return x;
    return fa[x]=find_(fa[x]);//合并
}
void dfs(int u){
    vis[u]=-1;//正数说明有环，0说明需要dfs，so将其置为负数
    ++num[u];//从链尾dfs每次给链尾+1
    for(auto&i:g[u]){
        num[i]=max(num[i],num[u]);//链尾以后的数字至少大于链尾（可能在别的链中数字较大），先让它们都和链尾相同以后再通过dfs++
        if(!--vis[i])
            dfs(i);
    }
}
void addedge(int u,int v){
    g[u].push_back(v);//建图
    vis[v]++;//打上标记
}
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n+m;i++)
        fa[i]=i;//初始化
    for(int i=1;i<=n;i++){
        scanf("%s",s[i]+1);
        for(int j=1;j<=m;j++)
            if(s[i][j]=='=')
                fa[find_(i)]=find_(n+j);//缩点
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            if(s[i][j]=='<')
                addedge(find_(i),find_(n+j));//大的放后面
            else if(s[i][j]=='>')
                addedge(find_(n+j),find_(i));//大的放后面
        }
    int flag=0;
    for(int i=1;i<=n+m;i++)
        if(find_(i)==i&&!vis[i])//找一个代表与它同值的所有点的点并且没有被拜访过即链尾
            dfs(i);//dfs
    for(int i=1;i<=n+m;i++)
        if(find_(i)==i&&vis[i]>0){//正值说明有环
            flag=1;
            printf("No");//显然有环是不能安排的
            break;
        }
    if(!flag){
        printf("Yes ");
        for(int i=1;i<=n;i++)
            printf("%d ",num[find_(i)]);//找到代表它的点的num值
        printf(" ");
        for(int i=1;i<=m;i++)
            printf("%d ",num[find_(i+n)]);//找到代表它的点的num值
    }
    return 0;
}