1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89
| #include<bits/stdc++.h> using namespace std; #define rep(i,a,n) for(int i=(a);i<(n);i++) #define per(i,a,n) for(int i=(n-1);i>=(a);i--) #define fi first #define se second typedef pair <int,int> pII; typedef long long ll; const int INF = 0x3f3f3f3f;
const int maxn = 2e3+10; vector<int> e[maxn];
int fa[maxn]; int Find(int x){ return fa[x] == x ? x : fa[x] = Find(fa[x]); } void Union(int i,int j){ int x = Find(i); int y = Find(j); if(x!=y) fa[x] = y; } int ind[maxn],use[maxn],vis[maxn]; char mx[maxn][maxn]; int n,m;
bool flag; int dp[maxn]; void dfs(int x,int dep){ if(flag) return ; dp[x] = max(dp[x],dep); for(auto to:e[x]){ if(vis[to]) { flag = true; return ; } if(dep+1>dp[to]){ vis[to] = 1; dfs(to,dep+1); vis[to] = 0; } } } int main(){ #ifdef LOCAL freopen("1.in","r",stdin); #endif scanf("%d%d",&n,&m); rep(i,0,n){ scanf("%s",mx+i); } rep(i,0,n+m) fa[i] = i; rep(i,0,n) rep(j,0,m) if(mx[i][j] == '=') Union(i,n+j); rep(i,0,n) rep(j,0,m){ int x = Find(i); int y = Find(j+n); if(mx[i][j] == '<'){ e[x].push_back(y); ind[y] ++; use[x] = 1; }else if(mx[i][j] == '>'){ e[y].push_back(x); ind[x] ++; use[y] = 1; }else{ use[x] = 1; } } bool fflag = false; rep(i,0,n+m){ if(use[i] && ind[i] == 0){ fflag = true; vis[i] = 1; dfs(i,1); vis[i] = 0; } } if(fflag == false || flag){ puts("No"); }else{ puts("Yes"); rep(i,0,n) printf("%d ",dp[Find(i)]); puts(""); rep(i,n,m+n) printf("%d ",dp[Find(i)]); } return 0; }
|