『算法-ACM 竞赛-图论』传递闭包（Floyd 模板）

图论–传递闭包（Floyd 模板）

#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
int dp[105][105],in[105],out[105];
int init()
{
    for(int i=1;i<=105;i++)
    {
        in[i]=0;
        out[i]=0;
        for(int j=1;j<=100;j++)
        {
            dp[i][j]=0;
        }
    }
}
int main()
{
    long long  t;
    cin>>t;
    while(t--)
    {
        init();
        long long n,m;
        cin>>n>>m;
        long long flag=0;
        for(int i=1;i<=m;i++)
        {
            long long  l,r;
            cin>>l>>r;
            dp[l][r]=1;
            if(l==r)    flag=1; //自己排在自己前面是不可能的，直接按题意输出0
        }
        for(int k=1;k<=n;k++)
            for(int i=1;i<=n;i++)
                for(int j=1;j<=n;j++)
                    dp[i][j]=(dp[i][k]&&dp[k][j]);//floyd 讨论图的连通性

        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                if(dp[i][j]==1&&dp[j][i]==1)
                    flag=1;
        //floyd 讨论图的连通性后，如果出现环的话，就是我排在你前面。你排在我前面，同样不可能
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                if(dp[i][j]==1)
                {
                    in[i]++;    //有几个人排在第I个人前面
                    out[j]++;//有几个人排在第j个人后面面
                }
        if(flag)  //不符合现实的按题意输出0
        {
            for(int i=1;i<=n;i++)cout<<"0";
            cout<<endl;
        }
        else
        {
            for(int i=1;i<=n;i++)
            {
                if(in[i]>=(n+1)/2||out[i]>=(n+1)/2)  cout<<"0";
                //如果在他前面或者在他后面的不等于一般的人数，他绝对不是中间位置
                else   cout<<"1";
            }
            cout<<endl;
        }
    }
    return 0;
 }