欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

P1347 排序 (拓扑排序)

程序员文章站 2022-03-20 13:06:20
题目 "P1347 排序" 解析 打开一看拓扑排序,要判环。 三种情况 有环(存在矛盾) 没环但在拓扑排序时存在有两个及以上的点入度为0(关系无法确定) 除了上两种情况(关系可确定) 本来懒了一下,直接在排序时判环,然后一直WA,遂怒写tarjan判环,第一个点注意特判两个点相同的情况,注意重边。 ......

题目

p1347 排序

解析

打开一看拓扑排序,要判环。
三种情况

  • 有环(存在矛盾)
  • 没环但在拓扑排序时存在有两个及以上的点入度为0(关系无法确定)
  • 除了上两种情况(关系可确定)

本来懒了一下,直接在排序时判环,然后一直wa,遂怒写tarjan判环,第一个点注意特判两个点相同的情况,注意重边。
然后就有了这又臭又长的

代码

#include <bits/stdc++.h>
using namespace std;
const int n = 1000;
int n, m, num, sum, tot;
int du[n], head[n], in[n], ans[n], dfn[n], low[n], size[n];
bool vis[n];
char s[n];

queue<int>q;
struct node {
    int v, nx;
} e[n];

template<class t>inline void read(t &x) {
    x = 0; int f = 0; char ch = getchar();
    while (!isdigit(ch)) f |= (ch == '-'), ch = getchar();
    while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
    x = f ? -x : x ;
    return;
}

inline void add(int u, int v) {
    for (int i = head[u]; ~i; i = e[i].nx) if (e[i].v == v) return;
    e[++num].nx = head[u], e[num].v = v, head[u] = num, in[v]++;
}

int topo() {
    int tmp = 0, cnt = 0;
    for (int i = 1; i <= n; ++i) if (!du[i]) q.push(i), tmp++;
    if (tmp > 1) return 0;
    while (!q.empty()) {
        tmp = 0, cnt++;
        int u = q.front(); q.pop();
        ans[cnt] = u;
        for (int i = head[u]; ~i; i = e[i].nx) {
            int v = e[i].v;
            du[v]--;
            if (!du[v]) q.push(v), tmp++;
        }
        if (tmp > 1) return 0;
    }
    return 1;
}

stack<int>sta;
void tarjan(int u) {
    dfn[u] = low[u] = ++tot;
    vis[u] = 1;
    sta.push(u);
    for (int i = head[u]; ~i; i = e[i].nx) {
        int v = e[i].v;
        if (!dfn[v]) tarjan(v), low[u] = min(low[u], dfn[u]);
        else if (vis[v]) low[u] = min(low[u], dfn[v]);
    }
    if (dfn[u] == low[u]) {
        int x = -1; sum++;
        while (x != u) {
            x = sta.top(), sta.pop();
            vis[u] = 0, size[sum]++;
        }
    }
}

int main() {
    memset(head, -1, sizeof head);
    read(n), read(m);
    for (int i = 1; i <= m; ++i) {
        scanf("%s", s);
        add(s[0] - 'a' + 1, s[2] - 'a' + 1);
        if(s[0] == s[2]) {
            printf("inconsistency found after %d relations.", i);
            return 0;
        }
        sum = tot = 0;
        memset(dfn, 0, sizeof dfn);
        memset(low, 0, sizeof low);
        memset(vis, 0, sizeof vis);
        memset(size, 0, sizeof size);
        for (int j = 1; j <= n; ++j) if (!dfn[j]) tarjan(j);
        for (int j = 1; j <= sum; ++j) if (size[j] > 1) {
            printf("inconsistency found after %d relations.", i);
            return 0;
        }
        memcpy(du, in, sizeof du);
        while (!q.empty()) q.pop();
        int k = topo();
        if (k == 1) {
            printf("sorted sequence determined after %d relations: ", i);
            for (int j = 1; j <= n; ++j) printf("%c", ans[j] + 'a' - 1);
            printf(".");
            return 0;
        } else continue;
    }
    printf("sorted sequence cannot be determined.");
    return 0;
}