AcWing 456. 车站分级 (虚拟节点优化二分图边数、拓扑序、差分约束、最长路）

#include<bits/stdc++.h>
using namespace std;
const int N=2010,M=1e6+10;
int n,m,e[M],ne[M],h[N],vis[N],dist[N],idx,w[M],d[N];
void add(int a,int b,int c){
    e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
    d[b]++;
}
vector<int>ans;
void tp(){
    queue<int>q;
    for(int i=1;i<=n+m;i++){
        if(!d[i])q.push(i);
    }
    while(!q.empty()){
        int x=q.front();
        q.pop();
        ans.push_back(x);
        for(int i=h[x];~i;i=ne[i]){
            int j=e[i];
            if(--d[j]==0){
                q.push(j);
            }
        }
    }
}
int main(){
    cin>>n>>m;
    memset(h,-1,sizeof h);
    for(int i=1;i<=m;i++){
        int x,st=n,ed=1,ver=n+i;
        memset(vis,0,sizeof vis);
        cin>>x;
        for(int j=1;j<=x;j++){
            int stop;
            cin>>stop;
            vis[stop]=1;
            st=min(st,stop),ed=max(ed,stop);
        }
        for(int j=st;j<=ed;j++){
            if(!vis[j])add(j,ver,0);
            else add(ver,j,1);
        }
    }
    tp();
    int res=-1;
    for(int i=1;i<=n;i++)dist[i]=1;
    //cout<<ans.size()<<endl;
    for(int i=0;i<ans.size();i++){
        int j=ans[i];
        //cout<<j<<endl;
        for(int k=h[j];~k;k=ne[k]){
            int x=e[k];
            dist[x]=max(dist[x],dist[j]+w[k]);
            //cout<<dist[x]<<endl;
            res=max(res,dist[x]);
        }
    }
    cout<<res<<endl;
}