#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\n");
for(int i=1;i<=n;i++)
printf("%d ",num[find_(i)]);//找到代表它的点的num值
printf("\n");
for(int i=1;i<=m;i++)
printf("%d ",num[find_(i+n)]);//找到代表它的点的num值
}
return 0;
}
Codeforces Round #541 (Div. 2)（并查集又称dsu，拓扑排序）
原文：https://www.cnblogs.com/ldudxy/p/10452845.html