P1347 sorting (topology + SPFA judgment ring or topology [inner judgment ring])

Sort

Title Description

An ascending sort sequence of different values refers to a sequence of increasing elements from left to right , for example , An ordered sequence of numbers $A,B,C,D$ Express $A<B,B<C,C<D$. In this question , We will give you a series of shapes such as $A<B$ The relationship between , And ask you to judge whether you can determine the order of this sequence according to these relationships .

Input format

The first line has two positive integers $n,m$,$n$ Indicates the number of elements to be sorted ,$2\le n\le 26$, The first $1$ To $n$ Elements will be capitalized $A,B,C,D\dots$ Express .$m$ Indicates the shape to be given, such as $A<B$ The number of relationships .

Next there is $m$ That's ok , Each row has $3$ Characters , Each is a capital letter , One < Symbol , A capital letter , Represents the relationship between two elements .

Output format

If according to the previous $x$ A relationship can determine this $n$ The order of the elements yyy..y（ Such as ABC）, Output

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

If according to the previous $x$ A relationship is found to be contradictory （ Such as $A<B,B<C,C<A$）, Output

Inconsistency found after x relations.

If according to this $m$ This relationship cannot be determined $n$ The order of the elements , Output

Sorted sequence cannot be determined.

（ Tips ： determine $n$ After the sequence of elements, the program can be ended , There is no need to consider the contradiction after determining the order ）

Examples #1

The sample input #1

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

Sample output #1

Sorted sequence determined after 4 relations: ABCD.

Examples #2

The sample input #2

3 2
A<B
B<A

Sample output #2

Inconsistency found after 2 relations.

Examples #3

The sample input #3

26 1
A<Z

Sample output #3

Sorted sequence cannot be determined.

Tips

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

Topology + spfa Judgment ring

Ideas ：

 Judge every time you add edges 
1.spfa Determine whether there is a ring 
2. Topological sorting to see if there is a solution 
Ⅰ. Check the number of elements in the stack before each stack , If more than 1, It shows that the relationship between them is uncertain .
Ⅱ. If the relationship is confirmed , Just record it , Cannot end program , There is also the possibility of contradictions .

Topology [ Inner judgment ring ]

Ideas

 1. Judge every time you add edges 
 2. A topological sort 
Ⅰ. Record ** Out of the stack ** Number sz, In a topological sort sz Less than 0, Explain that some points form a ring , Indicates that there is a contradiction , End the program directly after output .
Ⅱ. Check the number of elements in the stack before each stack , If more than 1, It shows that the relationship between them is uncertain .
Ⅲ. If the relationship is confirmed , Just record it , Cannot end program , There is also the possibility of contradictions .

Topology + spfa Judgment ring AC The code is as follows ：

#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();
}