题意
有两组菜，第一组有(n)种，第二组有(m)种。给出一个(n imes m)的矩阵，第(i)行第(j)列表示第一组中的第(i)种菜与第二组中的第(j)种菜好吃程度的比较。
如果为('>')表示第一组中的第(i)种菜比第二组种的第(j)种菜更好吃。
如果为('<')，表示第二组种的第(j)种菜比第一组中的第(i)种菜更好吃。
如果为('=')，表示两种菜同样好吃。
现在要给每种菜打上一个评分，要求好吃的菜的评分一定要比不好吃的更高。同样好吃的两种菜评分要相同。
第一行输出("YES")表示可以完成。并在下面两行分别输出两组菜的评分。
如果无法完成，输出一行"NO"
思路
并查集+拓扑排序
首先把所有的相等的菜放到一个并查集里面去。
然后从不好吃的菜向好吃的连边。然后开始拓扑排序。
对于每道菜，比他更好吃的菜的评分都是他的评分(+1)，如果无法拓扑，说明存在环，输出("NO")即可。
代码
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<cstring>
#include<queue>
#include<bitset>
using namespace std;
typedef long long ll;
const int N = 3010;
ll read() {
ll x=0,f=1;char c=getchar();
while(c<'0'||c>'9') {
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9') {
x=x*10+c-'0';
c=getchar();
}
return x*f;
}
char s[N][N];
int vis[N],ans[N];
queue<int>q;
struct node {
int v,nxt;
}e[N * N];
int fa[N];
int head[N],ejs;
void add(int u,int v) {
e[++ejs].v = v;e[ejs].nxt = head[u];head[u] = ejs;
}
int du[N];
int find(int x) {
return fa[x] == x ? x : fa[x] = find(fa[x]);
}
void uni(int x,int y) {
x = find(x),y = find(y);
if(rand() & 1) swap(x,y);
fa[x] = y;
}
int main() {
int n = read(),m = read();
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] == '=') uni(i,j + n);
}
}
for(int i = 1;i <= n;++i) {
for(int j = 1;j <= m;++j) {
int x = find(i),y = find(j + n);
if(s[i][j] == '<') {
if(x == y) {
puts("NO");
return 0;
}
add(x,y);
du[y]++;
}
else if(s[i][j] == '>') {
if(x == y) {
puts("NO");return 0;
}
add(y,x);
du[x]++;
}
}
}
int tot = 0;
for(int i = 1;i <= n + m;++i) {
int x = find(i);if(vis[x]) continue;
tot++;
vis[x] = 1;
if(!du[x]) q.push(x),ans[x] = 1;
}
while(!q.empty()) {
int u = q.front();q.pop();tot--;
for(int i = head[u];i;i = e[i].nxt) {
int v = e[i].v;du[v]--;
if(!du[v]) q.push(v),ans[v] = ans[u] + 1;
}
}
if(tot) {
puts("NO");return 0;
}
puts("YES");
for(int i = 1;i <= n;++i)
printf("%d ",ans[find(i)]);
puts("");
for(int i = 1;i <= m;++i)
printf("%d ",ans[find(i + n)]);
return 0;
}