AcWing 343. 排序 Floyd + 拓扑序    原题链接    简单

作者： 作者的头像   Tizzi ,  2020-01-31 22:26:11 ,  所有人可见 ,  阅读 1607

8


3 
#include <cstdio>
#include <cstring>
#include <queue> 
#include <iostream>
using namespace std;
const int N = 26;
int n, m, t, d[N][N], g[N][N], in[N]; //有无向边就代表关系出错 若一个点能够到达其他所有边那么排序完成 执行一次拓扑序即可 
char s[4];
void floyd() {
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                //i-->k有边 且 k-->j有边 那么i-->j有边 
                if (g[i][k] && g[k][j]) g[i][j] = 1;  
            }
        }
    }
}
void topsort() {
    queue<int> q;
    for (int i = 0; i < n; i++) if (!in[i]) q.push(i);
    printf("Sorted sequence determined after %d relations: ", t);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        printf("%c", (char)('A' + u)); 
        for (int v = 0; v < n; v++) {
            if (d[u][v]) { //查找的时候我们应按照非闭包图来求 
                in[v]--;
                if (!in[v]) q.push(v);
            }
        }
    }
    printf(".\n");
}
int main() {
    while (scanf("%d%d", &n, &m), n) {
        memset(g, 0, sizeof(g)); //0代表没有边 1代表有边 、
        memset(d, 0, sizeof(d));
        memset(in, 0, sizeof(in));
        bool find = false, fail = false; //若为true代表找到一种序列 
        for (int j = 1; j <= m; j++) {
            scanf("%s", s);
            if (find || fail) continue; //就不用继续查找了 
            int u = s[0] - 'A'; //A < B 那么建立一条A->B的边 若出现双向边代表出错 
            int v = s[2] - 'A';
            in[v]++;//入度增加 
            g[u][v] = d[u][v] = 1; //求一次floyd   
            floyd(); 
            //检查一下
            find = true; //假定找到了 
            for (int u = 0; u < n; u++) {
                if (g[u][u]) { //代表出现了 A < A 
                    fail = true; //存在双向边 状态出错了 
                    break;
                }
                for (int v = 0; v < n; v++) {
                    //必须满足 其中一个为0 一个为1 若2个都为0 0 或 1 1则不合法 
                    if (u != v && (!g[u][v] && !g[v][u])) find = false;//代表有一条边不连通 
                }
            } 
            t = j; 
        }
        if (fail) printf("Inconsistency found after %d relations.\n", t);
        else if (find) topsort();
        else printf("Sorted sequence cannot be determined.\n");
    }
    return 0;
}

3 评论

用户头像
acao8864   2021-02-19 11:49      1    踩      回复

直接拓扑排序会更快一些吧。

#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
int cnt, n, m, type, d[26], f[26];
bool st[26];

void topsort(int i, vector<int> graph[]) {
    queue<int> q;
    memcpy(d, f, sizeof f);
    for (int i = 0; i < n; ++i) {
        if (d[i] == 0) q.push(i);
    }
    string ans;
    bool unique = true;
    while (!q.empty()) {
        if (q.size() > 1) {
            unique = false;
        }
        int cur = q.front();
        char ch = 'A' + cur;
        ans += ch;
        q.pop();
        for (int ne : graph[cur]) {
            if (--d[ne] == 0) q.push(ne);
        }
    }
    if (ans.size() < cnt) {
        type = 2;
        printf("Inconsistency found after %d relations.\n", i);
    }
    if (ans.size() == n && unique) {
        type = 1;
        printf("Sorted sequence determined after %d relations: %s.\n", i, ans.c_str());
    }
}


int main() {
    string s;
    while (cin >> n >> m, n || m) {
        memset(f, 0, sizeof f);
        memset(st, 0, sizeof st);
        type = 0;
        cnt = 0;
        vector<int> graph[26];

        for (int i = 1; i <= m; ++i) {
            cin >> s;
            if (type) continue;
            int a = s[0] - 'A', b = s[2] - 'A';
            if (!st[a]) {
                st[a] = true;
                ++cnt;
            }
            if (!st[b]) {
                st[b] = true;
                ++cnt;
            }
            graph[a].push_back(b);
            f[b]++;
            topsort(i, graph);
        }
        if (!type) printf("Sorted sequence cannot be determined.\n");
    }
    return 0;
}
用户头像
五人凑钱买课TG   2023-01-02 20:02         踩      回复

$hack$:
26 100
K<X
U<L
Y<H
U<Z
T<R
U<J
U<O
P<M
F<X
W<Y
U<N
I<C
S<M
F<T
Q<E
T<U
V<L
G<U
K<Z
Q<R
P<K
M<N
O<J
J<I
Y<G
L<M
F<T
X<K
B<C
H<D
E<Y
L<X
T<W
W<A
H<F
W<C
Z<D
E<F
N<Y
P<W
G<F
N<T
V<G
B<D
F<T
F<P
W<U
E<P
U<S
H<G
T<P
A<T
S<K
F<S
M<Y
V<T
G<M
O<P
G<Q
N<S
V<Z
Z<D
U<W
L<E
G<Q
A<X
O<Z
H<Z
X<Z
I<P
C<O
O<B
R<X
C<U
E<J
A<V
N<M
A<B
W<R
N<J
F<C
T<G
V<Z
V<X
E<T
R<F
P<F
A<Y
E<P
I<O
A<X
H<T
H<T
M<L
K<A
U<G
L<J
G<F
V<M
A<C
0 0
输出：
Inconsistency found after 28 relations.

用户头像
五人凑钱买课TG   2023-01-02 20:21         踩      回复

把判重的st数组删掉就A了