用floyd求传递闭包

#include<bits/stdc++.h>
using namespace std;
const int maxn=26+1;
int n,m;
int a[maxn][maxn],b[maxn][maxn];
int floyd()
{
    memcpy(b,a,sizeof(b));
    for(int k=0;k<n;k++)
    {
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                b[i][j]|=b[i][k]&b[k][j];
                if(b[i][j]==b[j][i]&&b[i][j]==1&&i!=j)
                {
                    return -1;
                }
            }
        }
    }
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            if(b[i][j]==b[j][i]&&b[i][j]==0&&i!=j)
            {
                return 0;
            }
        }
    }
    return 1;
}
int main()
{
    while(cin>>n>>m&&(n!=0||m!=0))
    {
        char s[3];
        bool f=true;
        memset(a,0,sizeof(a));
        for(int i=0;i<m;i++)
        {
            cin>>s;
            if(s[1]=='<')
            {
                a[s[0]-'A'][s[2]-'A']=1;
            }
            else
            {
                a[s[2]-'A'][s[0]-'A']=1;
            }
            int now=floyd();
            if(f==false)
            {
                continue;
            }
            if(now==-1)
            {
                f=false;
                cout<<"Inconsistency found after "<<i+1<<" relations."<<endl;
            }
            else if(now==1)
            {
                f=false;
                cout<<"Sorted sequence determined after "<<i+1<<" relations: ";
                vector<pair<int,char> > c(n);
                for(int j=0;j<n;j++)
                {
                    c[j].first=0;
                    c[j].second=j+'A';
                }
                for(int k=0;k<n;k++)
                {
                    for(int j=0;j<n;j++)
                    {
                        c[k].first+=b[k][j];
                    }
                }
                sort(c.begin(),c.end());
                for(int i=n-1; i>=0; i--)
                {
                    cout<<c[i].second;
                }
                cout<<"."<<endl;
            }
        }
        if(f==true)
        {
            cout<<"Sorted sequence cannot be determined."<<endl;
        }
    }
    return 0;
}

题目地址：https://ac.nowcoder.com/acm/contest/1055/E