lp1983 NOIP2013 车站分级

看到\(DAG\)，立刻可以考虑上一个拓扑排序。
将偏序关系转化为邻接矩阵即可。

#include<iostream>
#include<cstdio>
#include<math.h>
#include<string.h>
#include<algorithm>
#include<queue>
using namespace std;
int n,m,s[1005][1005],in[1005],ans=0;
bool map[1005][1005],a[1005],d[1005],used[1005];
queue <int> q;

void re(){
	while(1){
		bool bo=0;
		for(int i=1;i<=n;i++){
			if(!in[i]&&!used[i]){
				q.push(i);
				used[i]=1;
				bo=1;
			}
		}
		if(!bo){
			break;
		}
		while(!q.empty()){
			int p=q.front();
			q.pop();
			for(int i=1;i<=n;i++){
				if(map[p][i]){
					map[p][i]=0;
					in[i]--;
				}
			}
		}
		ans++;
	}
}

int init(){
	memset(in,0,sizeof(in));
	scanf("%d %d",&n,&m);
	for(int i=1;i<=m;i++){
		scanf("%d",&s[i][0]);
		memset(a,0,sizeof(a));
		for(int j=1;j<=s[i][0];j++){
			scanf("%d",&s[i][j]);
			a[s[i][j]]=1;
		}
		for(int j=s[i][1];j<=s[i][s[i][0]];j++){
			if(!a[j]){
				for(int k=1;k<=s[i][0];k++){
					//map(i,j)表示i<j
					if(!map[j][s[i][k]]){
						map[j][s[i][k]]=1;
						in[s[i][k]]++;
					}
				}
			}
		}
	}
}

int main(){
	init();
	re();
	printf("%d",ans);
}