P1347 排序

题意看起来稍微有点复杂,还好数据很弱,可以放心进行各种处理.

这里的关系具有方向性,用图存储.A>B存储为一条A→B的边.

当给定一些关系后,只可能存在三种状态:

• 关系出现了环
• 关系没有环,且进行拓扑排序时每"层"只会发现一个入度为0的点,且图是联通的
• 上述状态之外的状态

只要已知的关系还没有出现环,那么只要之后给出足够多的关系总是有可能得出一种正确的排序.而只要出现了环,就已经发生了错误.

在尚未出现环的情况下,只要发现图联通且拓扑排序的每"层"总是只有一个入度为0的点,就已经找到了解,否则需要加入更多的关系.

很容易就可以写出来这样的流程,每一种要进行的判断和操作都很容易实现,只是有点繁琐.

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
using namespace std;

vector<int> s[30];
bool used[30], exist[30];
int n, m, fa[30], deg[30], tmp[30];

int get(int x) { return fa[x] == x ? x : fa[x] = get(fa[x]); }
void merge(int x, int y) { fa[get(y)] = fa[get(x)]; }
bool dfs(int x) {  // check circle
    if (!x) return true;
    // printf("DFSING %c 
", x + 'A' - 1);
    used[x] = true;

    for (auto i : s[x])
        if (used[i])
            return true;
        else if (dfs(i))
            return true;

    used[x] = false;
    return false;
}
int check() {  // Finish - 1       bad - -1        continue - 0
    bool good = true;  // check 1
    used[30] = {0};  // check -1
    int head = 0;
    for (int i = 1; i <= n; i++){
        if (exist[i] && !deg[i]) {
            if(head)
                good = false;
            head = i;
        }
        if (dfs(i)) return -1;
    }

    int base = 0, ct = 0;
    for (int i = 1; i <= n; i++) {
        if (!exist[i])
            continue;
        else
            ct++;
        if (!base) base = i;
        if (get(base) != get(i)) {
            good = false;
            break;
        }
    }
    if (good) {
        memcpy(tmp, deg, sizeof(deg));
        queue<int> q;
        q.push(head);
        while (!q.empty()) {
            if (q.size() > 1) return 0;
            int cur = q.front();
            q.pop();
            for (auto i : s[cur]) {
                tmp[i]--;
                if (!tmp[i]) q.push(i);
            }
        }
        if (q.size() > 1) return 0;
        if (ct == n)
            return 1;
        else
            return 0;
    }
    return 0;
}

int main() {
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    for (int i = 1; i <= 30; i++) fa[i] = i;
    cin >> n >> m;
    char x, y, opr;

    for (int i = 1; i <= m; i++) {
        cin >> x >> opr >> y;
        exist[x - 'A' + 1] = exist[y - 'A' + 1] = true;
        if (opr == '>') {
            s[x - 'A' + 1].push_back(y - 'A' + 1);
            deg[y - 'A' + 1]++;
        } else {
            s[y - 'A' + 1].push_back(x - 'A' + 1);
            deg[x - 'A' + 1]++;
        }
        merge(x - 'A' + 1, y - 'A' + 1);

        // printf("%d CHECKING MERGED %c %c
", i, x, y);
        int stat = check();
        if (stat == 1) {
            printf("Sorted sequence determined after %d relations: ", i);
            int head = 0;
            for (int i = 1; i <= n; i++)
                if (!deg[i]) {
                    head = i;
                    break;
                }
            queue<int> q;
            stack<int> ans;
            q.push(head);
            while (!q.empty()) {
                int cur = q.front();
                q.pop();
                ans.push(cur);
                for (auto i : s[cur]) {
                    deg[i]--;
                    if (!deg[i]) q.push(i);
                }
            }
            while (!ans.empty()) {
                printf("%c", ans.top() + 'A' - 1);
                ans.pop();
            }
            puts(".");
            return 0;
        } else if (stat == -1) {
            printf("Inconsistency found after %d relations.
", i);
            return 0;
        }
    }
    puts("Sorted sequence cannot be determined.");

    return 0;
}

实际上,判断图中有无环只需要检查拓扑排序后是否存在未遍历的点.