先把 = 的人用并查集合并在一起。
然后 < > 的建边, 跑一遍 toposort 之后就好了。
入度为0点的值肯定为1, 然后就是因为这个是按照时间线走过来的,所以一个点的最小值,就是在入队的那一刻确定的, 即入度为0的时候,值就是现在的值+1。
注意就是不要同一个点入队多次。
代码:
/* code by: zstu wxk time: 2019/02/24 */ #include<bits/stdc++.h> using namespace std; #define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout); #define LL long long #define ULL unsigned LL #define fi first #define se second #define pb push_back #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define lch(x) tr[x].son[0] #define rch(x) tr[x].son[1] #define max3(a,b,c) max(a,max(b,c)) #define min3(a,b,c) min(a,min(b,c)) typedef pair<int,int> pll; const int inf = 0x3f3f3f3f; const int _inf = 0xc0c0c0c0; const LL INF = 0x3f3f3f3f3f3f3f3f; const LL _INF = 0xc0c0c0c0c0c0c0c0; const LL mod = (int)1e9+7; const int N = 2e3 + 100; int pre[N]; int ind[N]; int val[N]; int n, m; char s[N][N]; vector<int> vc[N]; int Find(int x){ if(x == pre[x]) return x; return pre[x] = Find(pre[x]); } queue<int> q; void toposort(){ for(int i = 1; i <= n+m; ++i){ // cout << i << ' ' << ind[i] << endl; if(i == Find(i) && ind[i] == 0) { q.push(i), val[i] = 1; // cout << i << endl; } } while(!q.empty()){ int x = q.front(); q.pop(); for(int v : vc[x]){ ind[v]--; if(ind[v] == 0){ val[v] = val[x] + 1; q.push(v); } } } } void Ac(){ for(int i = 1; i <= n + m; ++i) pre[i] = i, ind[i] = 0; for(int i = 1; i <= n; ++i){ scanf("%s", s[i]+1); for(int j = 1; j <= m; ++j){ if(s[i][j] == '='){ int u = Find(i), v = Find(n+j); if(u == v) continue; pre[u] = v; } } } for(int i = 1; i <= n; ++i){ for(int j = 1; j <= m; ++j){ if(s[i][j] == '=' ) continue; int u = Find(i), v = Find(n+j); if(s[i][j] == '<'){ vc[u].pb(v); ind[v]++; } else { vc[v].pb(u); ind[u]++; } } } toposort(); for(int i = 1; i <= n+m; ++i){ if(!val[Find(i)]){ puts("No"); return ; } } puts("Yes"); for(int i = 1; i <= n; ++i){ printf("%d%c", val[Find(i)]," \n"[i==n]); } for(int i = 1; i <= m; ++i){ printf("%d%c", val[Find(i+n)], " \n"[i==m]); } } int main(){ while(~scanf("%d%d", &n, &m)){ Ac(); } return 0; }View Code