【题解】牛牛大力士

题意

有个选手和场比赛的结果，让你求编号为的选手可能的排名。

题解

场比赛的结果可以看作个偏序结构，可以构造一个有向图。那么可能在位置，就是对这个图进行拓扑排序，在拓扑排序中可能排在第几位。那么如果直接进行枚举所有可能的拓扑排序序列的话，时间复杂度是阶乘级别的，这样做肯定会超时。那么我们分析一下拓扑排序的性质。若某一个节点可以用来排序了，那么该点的入度肯定为0了。那么该点的最早能够被排序也需要对其有入度的节点进行排序完之后才能进行。也就是说若反向建图之后，点至少要排在，从点出发所能遍历的点的个数+1的位置。而最大排在哪里呢，就是正向建图后，-从出发所能遍历的节点个数。这相当于除了这部分子图之外，我们把其他的点都给排完了最后再来排这个点。所以只用跑两个dfs来求出点入度的子图大小和出度的子图大小即可。

复杂度

时间复杂度
空间复杂度

代码

#include<bits/stdc++.h>
using namespace std;
const int N=105;
int G1[N][N];
int G2[N][N];
int n,m,p;
int vis[N];
void dfs1(int u)
{
    for(int i=1;i<=n;i++)
    {
        if(vis[i]==0&&G1[u][i]==1)
        {
            vis[i]=1;
            dfs1(i);
        }
    }
}
void dfs2(int u)
{
    for(int i=1;i<=n;i++)
    {
        if(vis[i]==0&&G2[u][i]==1)
        {
            vis[i]=1;
            dfs2(i);
        }
    }
}
int main()
{
    scanf("%d%d%d",&n,&m,&p);
    for(int i=0; i<m; i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        G1[u][v]=1;
        G2[v][u]=1;
    }
    int l,r;
    l=1;
    r=n;
    dfs1(p);
    for(int i=1;i<=n;i++)
        if(vis[i])
            r--;
    memset(vis,0,sizeof(vis));
    dfs2(p);
    for(int i=1;i<=n;i++)
        if(vis[i])
            l++;
    for(int i=l;i<=r;i++)
        printf("%d ",i);
    printf("\n");
    return 0;
}