洛谷 P1983 [NOIP2013 普及组] 车站分级（拓扑排序）

题目传送门

解题思路

对于每一趟列车，我们可以知道其中没有经过的车站的级别肯定会比经过的车站的级别低。

于是，我们可以根据这种关系来建一个图。

将等级小的车站往等级大的车站建边。

于是，我们可以发现这是一个 DAG （有向无环图），

所以我们可以拓扑排序。

我们从等级最小的车站开始（也就是入度为  的车站），进行拓扑排序，每次记录经过的车站数量，然后找出最大等级的车站就可以了。

代码

#include<bits/stdc++.h>
using namespace std;

int n,m;
int a[1001],flag[1001];
bool lt[1001][1001];
vector<int> g[1001];
int d[1001],ans;
void tuopu()//拓扑排序 
{
	queue<pair<int,int> > q;
	for(int i=1;i<=n;i++)
	{
		if(d[i]==0)
			q.push(make_pair(i,1));
	}
	ans=1;
	while(!q.empty())
	{
		int u=q.front().first;
		int v=q.front().second;
		q.pop();
		for(auto y:g[u])
		{
			d[y]--;
			if(d[y]==0)
			{
				q.push(make_pair(y,v+1));
				ans=max(ans,v+1);
			}
		}
	}
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin>>n>>m;
	int l;
	for(int i=1;i<=m;i++)
	{
		cin>>l;
		memset(flag,0,sizeof flag);
		for(int j=1;j<=l;j++)
		{
			cin>>a[j];
			flag[a[j]]=1;//标记经过了的车站 
		}
		for(int j=a[1];j<=a[l];j++)
		{
			if(!flag[j])
			{
				for(int k=1;k<=l;k++)
				{
					if(!lt[j][a[k]])//判断是否有重复加边 
					{
						lt[j][a[k]]=1;//从没有经过的车站往经过的车站建图 
						g[j].push_back(a[k]);
						d[a[k]]++;
					}
				}
			}
		}
	}
	
	tuopu();
	
	cout<<ans;
	return 0;
}