题目大意:

中文题就不重复叙述了。我才不是战五渣!

分析:

把每个同学看成是一个点,每一场比赛看成是一条有向边,那么,如果有环就说明小明的猜想错了。然后就是如果没错,如何确定每个人的排名。求拓扑序可以用floyd求出来,时间复杂度O(n^3)可以接受。

关于用floyd求拓扑序:

就是如果对于排序集合中的任意两个元素,我都知道了他们的大小关系,那么我就可以说我知道了这个集合的拓扑序。两个点之间有一条有向边a–>b就说明了我知道他们之间的大小关系,我一个floyd下去,就知道了各个能确定的点的关系。然后我怎么知道会不会有环也就是互相矛盾的大小关系呢,就是看有没有双向边。然后怎么知道一个元素是不是已经确定了他的位置,就是看这个点和其他所有点的关系是否都确定。

代码:

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#define inf 0x3f3f3f3f

using namespace std;

int n,m;
int map[200][200];
int main()
{
    int test;
    scanf("%d",&test);
    while(test--)
    {
        memset(map,0,sizeof(map));
        int a,b;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d",&a,&b);//a赢b 
            map[b][a]=1;
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                for(int k=1;k<=n;k++)
                {
                    if(map[j][i]==1&&map[i][k]==1)
                    {
                        map[j][k]=1;
                    }
                }
            }
        }
        int flag=0;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(map[j][i]==1&&map[i][j]==1)
                {
                    flag=1;
                    break;
                }
            }
            if(flag==1)break;
        }
        if(flag==1)
        {
            printf("Wrong\n");
            continue;
        }
        int num=0;
        int is_sure1=1;
        for(int i=1;i<=n;i++)//判断i号点是不是确定的 
        {
            int is_sure=1;
            for(int j=1;j<=n;j++)
            {
                if(i==j)continue;
                if(map[i][j]==0&&map[j][i]==0)
                {
                    is_sure=0;
                    break;
                }
            }
            if(is_sure==1)num++;
        }
        int rank=1;
        for(int i=2;i<=n;i++)
        {
            if(map[1][i]==1)
            {
                rank++;
                continue;
            }
            if(map[i][1]==0)
            {
                is_sure1=0;
                break;
            }
        }
        if(is_sure1==0) printf("-1\n");
        else printf("%d\n",rank);
        printf("%d\n",num);
    }
}