POJ 1094 Sorting It All Out

题意：给出m对关于n个字母的小于关系，输出通过这些关系能得到的结论，如果可以排序就输出至少知道第几个关系时就可以知道顺序，从小到大输出顺序；如果产生歧义就输出在第几个关系时出现歧义，如果不能得出准确的大小关系就输出无法排序。

解法：拓扑排序。拓扑排序的大致流程就是先找入度为0的点，然后删去跟这个点相邻的边，再继续找入度为0的点，如果能一直找下去直到删掉所有边，则说明拓扑有序，否则拓扑无序。对于这道题，1.如果每次找到的入度为0的点有且只有一个且拓扑有序，则说明已有确定的顺序；2.如果找不到入度为0的点且还没删掉所有边则说明有环，即产生歧义；3.如果出现某一次找到的入度为0的点超过1个且拓扑有序，则说明还没有确定的顺序。

综合以上几点和网上的一些题解，有如下结论：

1.在拓扑排序的时候必须遍历整个图才可以得出结论，不可以发现入度为0的点超过1时就认为无法排序，还可能是产生歧义，此处注意上述第三条加粗部分。

2.题目中貌似（可能是我没看见）没说如果歧义出现在可以排序之后算歧义还是可以排序，我现在可以确定是算可以排序。

就这些了吧……貌似

代码：

#include<stdio.h>

#include<iostream>

#include<algorithm>

#include<string>

#include<string.h>

#include<math.h>

#include<limits.h>

#include<time.h>

#include<stdlib.h>

#include<map>

#include<queue>

#include<set>

#include<stack>

#include<vector>

#define LL long long

using namespace std;

int n, m;

string sorted;

int indegree[30];

vector <int> edge[30];

int topoSort()

{

    int degree[30];

    memcpy(degree, indegree, sizeof degree);

    stack <int> s;

    for(int i = 0; i < n; i++)

        if(degree[i] == 0) s.push(i);

    int res = 1;

    int cnt = 0;

    sorted.clear();

    while(!s.empty())

    {

        cnt++;

        if(s.size() > 1) res = 0;

        int tmp = s.top();

        sorted += ('A' + tmp);

        s.pop();

        for(int i = 0; i < edge[tmp].size(); i++)

        {

            if(--degree[edge[tmp][i]] == 0) s.push(edge[tmp][i]);

        }

    }

    if(cnt == n)

        return res;

    else return -1;

}

int main()

{

    while(~scanf("%d%d", &n, &m) && !(n == 0 && m == 0))

    {

        memset(indegree, 0, sizeof indegree);

        for(int i = 0; i < 26; i++) edge[i].clear();

        int ans = 0, pos = m;

        for(int i = 0; i < m; i++)

        {

            char input[5];

            scanf("%s", input);

            if(!ans)

            {

                edge[input[0] - 'A'].push_back(input[2] - 'A');

                indegree[input[2] - 'A']++;

                ans = topoSort();

            }

            else pos = min(i, pos);

        }

        if(ans == 1)

            cout << "Sorted sequence determined after " << pos << " relations: " << sorted << "." << endl;

        else if(ans == -1)

            cout << "Inconsistency found after " << pos << " relations." << endl;

        else

            cout << "Sorted sequence cannot be determined." << endl;

    }

    return 0;

}

巴特西

POJ 1094 Sorting It All Out

最新文章

热门文章