莫欺少年穷，修魔之旅在这开始—>算法提高课题解

思路：

1. 对于每次输入一对关系，如果目前还未确定两两之间的关系，我们都要重新确定两两之间的关系
2. 如果有矛盾，说明存在 d[i][i] = 1
3. 如果可以确定两两之间关系，则 d[i][j] 或 d[j][i] 之间必有一个是 1

#include<bits/stdc++.h>

using namespace std;

const int N = 26;

int n,m;
int g[N][N],d[N][N];
bool st[N];

void floyd()
{
    memcpy(d,g,sizeof d);

    for(int k=0;k<n;k++)
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                d[i][j]|=d[i][k]&&d[k][j];
}

int check()
{
    //有矛盾
    for(int i=0;i<n;i++)
        if(d[i][i])
            return 2;

    //不能确定两两之间的关系
    for(int i=0;i<n;i++)
        for(int j=0;j<i;j++)
            if(!d[i][j]&&!d[j][i])
                return 0;

    //已经确定两两之间的关系了
    return 1;
}

//找出最小字符
char get_min()
{
    for(int i=0;i<n;i++)
        if(!st[i])
        {
            bool flag=true;
            for(int j=0;j<n;j++)
                if(!st[j]&&d[j][i])
                {
                    flag=false;
                    break;
                }

            if(flag) 
            {
                st[i]=true;
                return 'A'+i;
            }
        }
}

int main()
{
    while(cin>>n>>m,n||m)
    {
        //初始化 g 数组
        memset(g,0,sizeof g);

        int type=0,t;
        for(int i=1;i<=m;i++)
        {
            char str[4];
            cin>>str;

            //还未确定两两之间的关系
            if(!type)
            {
                g[str[0]-'A'][str[2]-'A']=1;
                floyd();
                type=check();
                if(type) t=i;
            }
        }

        //不能确定两两之间的关系
        if(!type) printf("Sorted sequence cannot be determined.\n");

        //在第 t 步有矛盾
        else if(type==2) printf("Inconsistency found after %d relations.\n",t);

        //可以在第 t 步确定两两之间的关系
        else 
        {
            //初始化 st 数组
            memset(st,0,sizeof st);

            //在第 t 步确定两两之间的关系
            printf("Sorted sequence determined after %d relations: ",t);

            //输出最小的字符
            for(int i=0;i<n;i++) printf("%c",get_min());
            printf(".\n");
        }
    }

    return 0;
}

不需要Floyd，优化了一维

#include<bits/stdc++.h>

using namespace std;

const int N = 26;

int n,m;
int d[N][N];
bool st[N];

int check()
{
    //有矛盾
    for(int i=0;i<n;i++)
        if(d[i][i])
            return 2;

    //不能确定两两之间的关系
    for(int i=0;i<n;i++)
        for(int j=0;j<i;j++)
            if(!d[i][j]&&!d[j][i])
                return 0;

    //已经确定两两之间的关系了
    return 1;
}

//找出最小字符
char get_min()
{
    for(int i=0;i<n;i++)
        if(!st[i])
        {
            bool flag=true;
            for(int j=0;j<n;j++)
                if(!st[j]&&d[j][i])
                {
                    flag=false;
                    break;
                }

            if(flag) 
            {
                st[i]=true;
                return 'A'+i;
            }
        }
}

int main()
{
    while(cin>>n>>m,n||m)
    {
        //初始化 d 数组
        memset(d,0,sizeof d);

        int type=0,t;
        for(int i=1;i<=m;i++)
        {
            char str[4];
            cin>>str;

            int a=str[0]-'A',b=str[2]-'A';

            //还未确定两两之间的关系
            if(!type)
            {
                d[a][b]=1;

                for(int x=0;x<n;x++)
                {
                    if(d[x][a]) d[x][b]=1;
                    if(d[b][x]) d[a][x]=1;

                    for(int y=0;y<n;y++)
                        if(d[x][a]&&d[b][y])
                            d[x][y]=1;
                }

                type=check();
                if(type) t=i;
            }
        }

        //不能确定两两之间的关系
        if(!type) printf("Sorted sequence cannot be determined.\n");

        //在第 t 步有矛盾
        else if(type==2) printf("Inconsistency found after %d relations.\n",t);

        //可以在第 t 步确定两两之间的关系
        else 
        {
            //初始化 st 数组
            memset(st,0,sizeof st);

            //在第 t 步确定两两之间的关系
            printf("Sorted sequence determined after %d relations: ",t);

            //输出最小的字符
            for(int i=0;i<n;i++) printf("%c",get_min());
            printf(".\n");
        }
    }

    return 0;
}