Luogu P1983 车站分级

#include<cstdio>
#include<queue>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

int n,m,s,stop[1005],head[1005],in[1005],dep[1005],ans,cnt;

bool tag[1005],vis[1005][1005];

struct edge{
    int v,next;
}e[1000005];

inline void add(int u,int v){
    e[++cnt].v=v;
    e[cnt].next=head[u];
    head[u]=cnt;
}

int main(){
    memset(head,-1,sizeof(head));
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        memset(tag,0,sizeof(tag));
        scanf("%d",&s);
        for(int j=1;j<=s;j++){
            scanf("%d",&stop[j]);
            tag[stop[j]]=1;
        }
        for(int j=stop[1];j<=stop[s];j++){
            if(!tag[j]){
                for(int k=1;k<=s;k++){
                    if(vis[j][stop[k]])continue;//防止建重边，因为e[1000005] 
                    add(j,stop[k]);
                    in[stop[k]]++;
                    vis[j][stop[k]]=1;
                }
            }
        }
    }
    queue<int> q;
    for(int i=1;i<=n;i++){
        if(!in[i]){
            q.push(i);
            in[i]=-1;
            dep[i]=1;
        }
    }
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i=head[u];i!=-1;i=e[i].next){
            int v=e[i].v;
            in[v]--;
            if(!in[v]){
                in[v]=-1;
                q.push(v);
                dep[v]=dep[u]+1;
                ans=max(ans,dep[v]);
            }
        }
    }
    printf("%d\n",ans);
}

Luogu P1983 车站分级

原文：https://www.cnblogs.com/Y15BeTa/p/11427709.html