拓扑板子

P1983 [NOIP2013 普及组] 车站分级

#include<bits/stdc++.h>
using namespace std;
struct node{int to,next;}bian[15000100];
int n,m,cnt,head[15000100],a[1010],ru[15000100];
void add(int x,int y){
	cnt++;
	bian[cnt].to=y;
	bian[cnt].next=head[x];
	head[x]=cnt;
}
int mcnt,sp,dui[100010];
void zhao(){
	for(int i=1;i<=n;i++)
		if(ru[i]==0)
			dui[sp++]=i;
}
void tuopu(){
	mcnt++;
	sp=1;zhao();
	if(sp==1)return ;
	for(int i=1;i<=sp-1;i++){
		for(int k=head[dui[i]];k;k=bian[k].next)
			ru[bian[k].to]--;
		ru[dui[i]]=-1;
	}
	tuopu();
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int s;cin>>s;
		for(int j=1;j<=n;j++)a[j]=0;
		int minn,maxn;//这一辆车的起点&终点 
		for(int j=1;j<=s;j++){
			int c;cin>>c;a[c]=1;
			if(j==1)minn=c;
			else if(j==s)maxn=c;
		}
//		cout<<minn<<' '<<maxn<<endl;
		for(int j=minn;j<=maxn;j++)
			for(int k=minn;k<=maxn;k++)
				if(a[j]==1&&a[k]==0){
					add(j,k);ru[k]++;
				}
	}
	tuopu();
	cout<<mcnt-1;
	return 0;
}