POJSorting It All Out (拓扑)

题目链接。

题目大意:

给定一定的数量的小于关系：

1.如果发现环，输出从前几次就可以确定出现环

2.如果能够确定唯一序列，输出。

3.如果通过全部关系，还不能确定序列，则输出不能确定.

分析:

个人感觉难点在于判环上。

1.如果每次都只能找到1个入度为0的点，并能确定序列，则该序列即为答案。

2.如果每次查找时，发现两个及其以上的入度为0的点，则表明一定不能确定唯一序列（即存在环或者是不能确定）。如果可以确定一个任意序列，即表明还需要更多关系。如果继续查找下去，找不到入度为0的点，则存在环。　

AC代码如下：

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <queue>

using namespace std;

const int maxn = ;

const int INF = (<<);

int n, m, indeg[maxn], S[maxn], top, mark;

bool G[maxn][maxn], v[maxn];

int toposort()

{

    int deg[maxn], cn;

    bool vis[maxn], flag = true;

    top = ;

    memcpy(deg, indeg, sizeof(deg));

    memset(vis, , sizeof(vis));

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

    {

        cn = ;

        for(int k=; k<n; k++) if(deg[k] == ) cn++;            //计算入度为0的点的个数

        if(cn > ) flag = false;                               //出现环或者不能确定唯一序列

        else if(cn == ) break;                               //出现环

        int k;

        for(k=; k<n; k++) if(deg[k] == ) break;

        S[top++] = k;

        deg[k]--;

        for(int j=; j<n; j++) if(G[k][j]) deg[j]--;

    }

    if(cn == ) return -;      //环

    if(mark < n || !flag) return ;      //不能判断

    else return ;   //拓扑成功

}

int main()

{

    char c1, c2;

    int flag, num;

  //  freopen("my.txt", "r", stdin);

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

    {

        if(n ==  && m == ) break;

        memset(indeg, , sizeof(indeg));

        memset(G, false, sizeof(G));

        memset(v, false, sizeof(v));

        flag = ;

        mark = ;

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

        {

            getchar();

            scanf("%c<%c", &c1, &c2);

            if(!G[c1-'A'][c2-'A']) {

                G[c1-'A'][c2-'A'] = true;

                indeg[c2-'A']++;

            }

            //mark用来标记当前已经出现的字母的个数

            if(!v[c1-'A']) { v[c1-'A'] = true; mark++; }

            if(!v[c2-'A']) { v[c2-'A'] = true; mark++; }

            int res;

            if(flag == ) {

                res = toposort();

                if(res == -) {

                    flag = -;

                    num = i;

                } else if(res == ) {

                    num = i;

                    flag = ;

                }

            }

        }

        if(flag == ) {

            printf("Sorted sequence determined after %d relations: ", num+);

            for(int i=; i<top; i++)

            {

                putchar(S[i]+'A');

            }

            printf(".\n");

        }

        else if(flag == ) printf("Sorted sequence cannot be determined.\n");

        else printf("Inconsistency found after %d relations.\n", num+);

    }

    return ;

}