Gourmet choice [Codeforces Round #541 (Div. 2) D]

https://codeforces.com/contest/1131/problem/D

N要素の配列X、M要素の配列Yを構築する。
A[x][y] := X[x]とY[y]の大小関係。＜ならX[x]＜Y[y]、＞ならX[x]＞Y[y]、=ならX[x]=Y[y]
配列Aが与えられたときに、配列X,Yを構築できるか判定し、できるなら構築せよ。
1≦N,M≦10^3

前提知識

• UnionFind
• トポロジカルソート

解説

https://codeforces.com/contest/1131/submission/50417587

配列X,Yの各要素のグラフの頂点として考え、大小関係に応じて有向辺を張ることを考える。
この考えに至ることがまず大変であるが、経験から辿り着いたとしか言えない。
後半については頻出であると思う。
　
このとき=の関係については頂点をUnionFindを使ってマージしておこう。
有向辺を張ったときにループが発生するなら、適切に数を割り当てても条件を満たすことはできない。
このDAGについて、大小関係を満たしながら数を割り当てるが、ちょうど深さを使えばよさそう。
深さの割り当ては、日経コンテストの予選Dでも出たが、遷移先に自分の深さ+1を割り当てていき、
複数割り当てられた場合は最大値を採用していけば、深さを正しく割り当てられる。

int N, M;
string S[1010];
#define no "No"
vector<int> E[2010];
int ans[2010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    rep(i, 0, N) cin >> S[i];

    UnionFind uf(N + M);
    rep(i, 0, N) rep(j, 0, M) if (S[i][j] == '=') uf(i, N + j);
    TopologicalSort ts(N + M);
    rep(i, 0, N) rep(j, 0, M) {
        if (S[i][j] == '=') continue;
        if (uf[i] == uf[N + j]) {
            cout << no << endl;
            return;
        }

        if (S[i][j] == '<') {
            ts.add_edge(uf[i], uf[N + j]);
            E[uf[i]].push_back(uf[N + j]);
        }
        else {
            ts.add_edge(uf[N + j], uf[i]);
            E[uf[N+j]].push_back(uf[i]);
        }
    }

    vector<int> ord;
    bool res = ts.sort(ord);
    if (!res) {
        cout << no << endl;
        return;
    }

    fore(cu, ord) {
        if (ans[cu] == 0) ans[cu] = 1;
        fore(to, E[cu]) chmax(ans[to], ans[cu] + 1);
    }

    printf("Yes\n");
    rep(i, 0, N) {
        if (i) printf(" ");
        printf("%d", ans[uf[i]]);
    }
    printf("\n");
    rep(i, 0, M) {
        if (i) printf(" ");
        printf("%d", ans[uf[N+i]]);
    }
    printf("\n");
}