0pts 7WA 3TLE 本地样例能过，请大佬帮忙看看

杨誉yy @ 2020-12-18 13:05:26

#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
queue <long long> ii;
int ans,n,i,j,t,head,m,s1,s2,k,tmp;
int num[2000],l[2000][2000],cnt[2000],up[2000],down[2000];
bool v[2000],vis[2000][2000];
int main()
{
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        s1=0;
        s2=0;
        memset(v,false,sizeof(v));
        scanf("%d",&tmp);
        for(j=1;j<=tmp;j++)
        {
            scanf("%d",&t);
            up[++s1]=t;
            v[t]=true;
        }
        for(j=1;j<=n;j++)
        {
            if(!v[i])
            {
                down[++s2]=i;
            }
        }
        for(j=1;j<=s2;j++)
        {
            for(k=1;k<=s1;k++)
            {
                if(!vis[down[j]][up[k]])
                {
                    l[down[j]][++cnt[down[j]]]=up[k];
                    num[up[k]]++;
                    vis[down[j]][up[k]]=vis[up[k]][down[j]]=true;
                }
            }
        }
    }
    for(i=1;i<=n;i++)
    {
        if(num[i]==0)
        {
            ii.push(i);
        }
    }
    while(n)
    {
        tmp=ii.size();
        for(i=1;i<=tmp;i++)
        {
            head=ii.front();
            ii.pop();
            for(j=1;j<=cnt[head];j++)
            {
                num[l[head][j]]--;
                if(num[l[head][j]]==0)
                {
                    ii.push(l[head][j]);
                }
            }
            n--;
        }
        ans++;
    }
    printf("%d",ans);
}

by BX、夔氂 @ 2020-12-18 15:01:43

有错误，需要改！！！

by 杨誉yy @ 2020-12-26 08:40:43

@BX、夔氂
卑微地问一下大佬哪里错了

by BX、夔氂 @ 2021-01-08 14:34:44

可以这样，（带题解）

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
#define pii pair<int,int>
const int e=1e3+5;
int s[e][e],n,m,ans,ru[e],vis[e],tot,pd[e][e];
queue<pii>q;
vector<int>g[e];
inline int getint()//读入优化
{
    char ch;
    int res=0;
    while(ch=getchar(),ch<'0'||ch>'9');
    res=ch-48;
    while(ch=getchar(),ch>='0'&&ch<='9')
    res=(res<<3)+(res<<1)+ch-48;
    return res;
}
inline void bfs()//拓扑排序 
{
    int i;
    for(i=1;i<=n;i++)
    if(ru[i]==0)
    q.push(make_pair(i,1));//没有入度，级别最低 
    ans=1;
    while(!q.empty())
    {
        int u=q.front().first,val=q.front().second;
        //队列中的每个元素有2个关键字，第一个是车站编号，第二个是级别
        q.pop();
        for(i=0;i<g[u].size();i++)
        {
            int v=g[u][i];
            ru[v]--;
            if(ru[v]==0)
            {
                q.push(make_pair(v,val+1));//递推，当前点的级别为val+1 
                ans=max(ans,val+1);//ans记录最高级别，也就是不同级别的数量 
            }
        }
    }
}
int main()
{
    int i,j,x;
    n=getint();
    m=getint();
    for(i=1;i<=m;i++)
    {
        s[i][0]=getint();//s[i][0]为车次i停靠的车站数量 
        memset(vis,false,sizeof(vis));
        for(j=1;j<=s[i][0];j++)
        {
            x=getint();
            s[i][j]=x;//s[i][j]表示车次i停靠的第j个车站 
            vis[x]=true;//当前车次有停靠x 
        }
        for(j=s[i][1];j<=s[i][s[i][0]];j++)//枚举经过的所有车站（不一定停靠） 
        {
            if(vis[j])continue;//这条路上所有不停靠的必须比所有停靠的级别低 
            for(int k=1;k<=s[i][0];k++)
            if(!pd[j][s[i][k]])//pd判断这条边是否还没连 
            {
                ru[s[i][k]]++;//入度+1 
                g[j].push_back(s[i][k]);
                //j向s[i][k]连边，表示j的级别必须比s[i][k]低 
                pd[j][s[i][k]]=true;//标记为连过的边 
            }
        }
    }
    bfs();
    cout<<ans<<endl;
    return 0;
}

by BX、夔氂 @ 2021-01-08 14:35:34

@杨誉yy

by 杨誉yy @ 2021-01-14 00:35:30

大概明白了，谢谢大佬 @BX、夔氂