-图论-拓扑排序- [CF1131D]Gourmet choice

题目描述

Link

Solution

并查集 + 拓扑排序

那么我们该怎样用并查集和拓扑排序呢

思路很简单，把标有=的i和j放在同一个并查集内，然后根据题意连边，如果是>，就这么连：i所在集合的标号 -> j所在集合的标号，如果是>那么就相反。当然，你也可以和我的意思相反，就是在赋值上有些麻烦。

连完边后，直接跑拓扑就可以了，别忘了在拓扑排序的时候给点赋值

也别忘了判断一下有没有环，如果有环，那么就不存在。

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#define MAXN 2000100
char mp[1010][1010];
int n, m, head[MAXN], ecnt, x, y, ent[MAXN], out[MAXN], rank[MAXN], p, deli[MAXN], fa[MAXN], ans, tot;
bool vis[MAXN], ifq[MAXN];
std::queue <int> q;
struct Edge {
    int v, nx;
}e[MAXN];
void add(int f, int t) {
    e[++ecnt] = (Edge) {t, head[f]};
    head[f] = ecnt;
}
int find(int x) {
    if (fa[x] == x) return x;
    else return fa[x] = find(fa[x]);
}
void un(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) return;
    if (rank[x] <= rank[y]) {
        fa[x] = y;
        if (rank[x] == rank[y]) {
            rank[x]++;
        }
    }
    else {
        fa[y] = x;
    }
    return;
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%s", mp[i] + 1);
    }
    for (int i = 1; i <= n + m; i++) {
        fa[i] = i;
        rank[i] = 1;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (mp[i][j] == '=') {
                un(i, j + n);
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            x = find(j + n);
            y = find(i);
            if (mp[i][j] == '>') {
                add(x, y);
                ent[y]++;
            }
            if (mp[i][j] == '<') {
                add(y, x);
                ent[x]++;
            }
        }
    }
    tot = n + m;
    for (int i = 1; i <= n + m; i++) {
        p = find(i);
        if (!ent[p] && !ifq[p]) {
            q.push(p);
            ifq[p] = 1;
            deli[p] = 1;
            deli[i] = 1;
        }
    }
    ans = 0;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        vis[u] = 1;
        for (int i = head[u]; i; i = e[i].nx) {
            int to = e[i].v;
            if (vis[to]) continue;
            ent[to]--;
            if (!ent[to]) {
                deli[to] = deli[u] + 1;
                q.push(to);
            }
        }
    }
    memset(vis, 0, sizeof(vis));
    for (int i = 1; i <= n + m; i++) {
        if (!ent[find(i)]) ans++;
    }
    // for (int i = 1; i <= n + m; i++) {
    // 	printf("%d ", ent[find(i)]);
    // }
    // puts("");
    if (tot != ans) {
        // printf("%d %d\n", tot, ans);
        puts("No");
        return 0;
    }
    puts("Yes");
    for (int i = 1; i <= n + m; i++) {
        int p = find(i);
        deli[i] = deli[p];
    }
    for (int i = 1; i <= n; i++) {
        printf("%d ", deli[i]);
    }
    puts("");
    for (int i = n + 1; i <= n + m; i++) {
        printf("%d ", deli[i]);
    }
    return 0;
}