codeforces 1131 D Gourmet choice （并查集缩点+拓扑排序）

• 等于，则将两个点加入并查集
• 大于，从j连一条有向边向i，因为后面要做的拓扑排序是以入度大小为顺序的，要让大的数尽量晚些入队，即使其入度尽量大
• 小于，从i连一条有向边向j，同上

• 内部用并查集边缩点边判环，根节点相同则内部成环
• 外部用最后度数判断，有度数不为0的点则外部成环

• 其实这类”程序自动分析“式题目，大多可以用并查集+连通块解决，我们需要找到题目中的”等价关系“（连通块），”边权关系“（连通块之间），以及”矛盾关系“（连通块内部以及连通块外部）
• 对于本题来说，”等价“关系指的是两个数相等，”边权关系“指的是数的大小关系，”矛盾关系“指的是连通块内部之间数的大小与相等的矛盾以及连通块外部之间的大小关系矛盾。

//#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<set>
#include<vector>
#include
<map>
#include<stack>
#include<queue>
#include<cmath>
#include<fstream>
#include<algorithm>
using namespace std;

#define rep(i,a,n) for(int i=a;i<=n;i++) #define per(i,a,n) for(int i=n;i>=a;i--)
#define CLR(a) memset(a,0,sizeof(a))

typedef long long ll;
typedef unsigned long long ull;

const int INF = 0x3f3f3f3f;

const int maxn=1010;




int n,m;
char g[maxn][maxn];
int pre[maxn*2];
int ans[maxn*2];
int deg[maxn*2];
vector<int>edge[maxn*2];
void init(){
	rep(i,1,n+m)pre[i]=i;
}
int Find(int x){
	return x==pre[x]?x:pre[x]=Find(pre[x]);
}
void Union(int x,int y){
	pre[Find(x)] = Find(y);
}

void toopsort(){
	CLR(deg);
	CLR(ans);
	rep(i,1,n+m){
		for(int j=0;j<edge[i].size();j++){
			++deg[edge[i][j]];
		}
	}
	queue<int>q;
	rep(i,1,n+m){
		//不用单独将连通块列出来，因为非缩的点不会有其余节点
		//这里如果将i换成Find(i)反而会导致重复入队 
		if(deg[i]==0)q.push(i*10000+1),ans[i]=1;
	}
	while(!q.empty()){
		int tmp=q.front();
		q.pop();
		int u = tmp/10000,step = tmp%10000;
		for(int i=0;i<edge[u].size();i++){
			if(--deg[edge[u][i]]==0)q.push(edge[u][i]*10000+step+1),ans[edge[u][i]]=step+1;	
		}
	}
}
int main(){
	scanf("%d %d", &n,&m);
	init();
	rep(i,1,n){
		scanf("%s", g[i]+1);
		rep(j,1,m){
			if(g[i][j]=='='){
				Union(i,n+j);
			}
		}
	}
	int flag=1;
	rep(i,1,n){
		rep(j,1,m){
			if(Find(i)==Find(n+j)&&g[i][j]!='='){
				flag=0;
				break;
			}
			if(g[i][j]=='<')edge[Find(i)].push_back(Find(n+j)); if(g[i][j]=='>')edge[Find(n+j)].push_back(Find(i));
		}
	}
	toopsort();
	rep(i,1,n){
		for(int j=0;j<edge[i].size();j++){ if(deg[edge[i][j]]>0){
				flag=0;
				break;
			}
		}
		if(!flag)break;
	}
	if(!flag){
		puts("No");
	}else{
		printf("Yes");
		rep(i,1,n)printf(" %d", ans[Find(i)]);
		printf(" ");
		rep(i,1,m)printf(" %d", ans[Find(n+i)]);
	}
	return 0;
}