[数据结构与算法]P1347 排序(拓扑 + spfa判断环 or 拓扑[内判断环])

排序

题目描述

一个不同的值的升序排序数列指的是一个从左到右元素依次增大的序列，例如，一个有序的数列 $A,B,C,D$ 表示$A<B,B<C,C<D$。在这道题中，我们将给你一系列形如 $A<B$ 的关系，并要求你判断是否能够根据这些关系确定这个数列的顺序。

输入格式

第一行有两个正整数 $n,m$，$n$ 表示需要排序的元素数量，$2\le n\le 26$，第 $1$ 到 $n$ 个元素将用大写的 $A,B,C,D\dots$ 表示。$m$ 表示将给出的形如 $A<B$ 的关系的数量。

接下来有 $m$ 行，每行有 $3$ 个字符，分别为一个大写字母，一个 < 符号，一个大写字母，表示两个元素之间的关系。

输出格式

若根据前 $x$ 个关系即可确定这 $n$ 个元素的顺序 yyy..y（如 ABC），输出

Sorted sequence determined after xxx relations: yyy...y.

若根据前 $x$ 个关系即发现存在矛盾（如 $A<B,B<C,C<A$），输出

Inconsistency found after x relations.

若根据这 $m$ 个关系无法确定这 $n$ 个元素的顺序，输出

Sorted sequence cannot be determined.

（提示：确定 $n$ 个元素的顺序后即可结束程序，可以不用考虑确定顺序之后出现矛盾的情况）

样例 #1

样例输入 #1

4 6
A<B
A<C
B<C
C<D
B<D
A<B

样例输出 #1

Sorted sequence determined after 4 relations: ABCD.

样例 #2

样例输入 #2

3 2
A<B
B<A

样例输出 #2

Inconsistency found after 2 relations.

样例 #3

样例输入 #3

26 1
A<Z

样例输出 #3

Sorted sequence cannot be determined.

提示

$2\le n\le 26,1\le m\le 600$。

拓扑 + spfa判断环

思路：

每一次加边都判断一下
1.spfa判断是否存在环
2.拓扑排序看是否已经发现有解
Ⅰ.检查每次出栈前栈中元素个数，若大于1，说明它们间关系未定。
Ⅱ.若关系确定，记录一下就好了，不能结束程序，还有出现矛盾的可能。

拓扑[内判断环]

思路

 1.每一次加边都判断一下
 2.拓扑排序
Ⅰ.记录**出栈**个数sz，一次拓扑排序中sz小于0，说明一些点构成了环，表示存在矛盾，输出后直接结束程序。
Ⅱ.检查每次出栈前栈中元素个数，若大于1，说明它们间关系未定。
Ⅲ.若关系确定，记录一下就好了，不能结束程序，还有出现矛盾的可能。

拓扑 + spfa判断环 AC代码如下：

#include <bits/stdc++.h>
#define buff                     \
    ios::sync_with_stdio(false); \
    cin.tie(0);
//#define int long long
using namespace std;
const int N = 1000;
int n, m;
map<char, int> mp;
char s[30];
int cntt;
vector<int> g[30];
bool st[30];
int dist[30], cnt[30];
int d[30];
int dd[30];
int q[30], tt = -1, hh = 0;
bool spfa()
{
    memset(dist, 0, sizeof dist);
    queue<int> q;
    for (int i = 1; i <= cntt; i++)
    {
        q.push(i);
        st[i] = true;
    }
    while (q.size())
    {
        int t = q.front();
        q.pop();

        st[t] = false;
        for (auto it : g[t])
        {
            if (dist[it] < dist[t] + 1)
            {
                dist[it] = dist[t] + 1;
                cnt[it] = cnt[t] + 1;

                if (cnt[it] >= cntt)
                    return true;
                if (!st[it])
                {
                    q.push(it);
                    st[it] = true;
                }
            }
        }
    }
    return false;
}
bool topusort()
{
    int emo = 0;
    for (int i = 1; i <= cntt; i++)
        dd[i] = d[i];
    tt = -1, hh = 0;
    for (int i = 1; i <= cntt; i++)
    {
        if (!dd[i])
            q[++tt] = i, emo++;
    }
    if (emo > 1)
        return 0;
    while (hh <= tt)
    {
        int emo = 0;
        int t = q[hh++];
        for (auto it : g[t])
        {
            dd[it]--;
            if (!dd[it])
                q[++tt] = it, emo++;
            if (emo > 1)
                return 0;
        }
    }

    return tt == n - 1;
}
void solve()
{
    cin >> n >> m;
    int flag = 0;
    int idx;
    for (int i = 1; i <= m; i++)
    {
        string a;
        cin >> a;
        if (!mp[a[0]])
        {
            mp[a[0]] = ++cntt;
            s[cntt] = a[0];
        }
        if (!mp[a[2]])
        {
            mp[a[2]] = ++cntt;
            s[cntt] = a[2];
        }

        g[mp[a[2]]].push_back(mp[a[0]]);
        d[mp[a[0]]]++;

        if (flag)
        {
            continue;
        }

        if (spfa())
        {
            flag = 1;
            idx = i;
            continue;
        }
        if (topusort())
        {
            idx = i;
            flag = 2;
            continue;
        }
    }
    if (flag == 1)
    {
        cout << "Inconsistency found after " << idx << " relations.\n";
        return;
    }

    if (flag == 2)
    {
        cout << "Sorted sequence determined after " << idx << " relations: ";
        for (int i = n - 1; i >= 0; i--)
            cout << s[q[i]];
        cout << ".\n";
    }

    if (flag == 0)
    {
        cout << "Sorted sequence cannot be determined.\n";
    }
}
int main()
{
    buff;
    solve();
}