拓扑入门之车站分级
题目链接；https://www.luogu.org/problem/P1983
题目
一条单向的铁路线上，依次有编号为 1,2,…,n1, 2, …, n 1,2,…,n的 nn n个火车站。每个火车站都有一个级别，最低为 111 级。现有若干趟车次在这条线路上行驶，每一趟都满足如下要求：如果这趟车次停靠了火车站 xxx，则始发站、终点站之间所有级别大于等于火车站x xx 的都必须停靠。（注意：起始站和终点站自然也算作事先已知需要停靠的站点）
例如，下表是5 5 5趟车次的运行情况。其中，前4 44 趟车次均满足要求，而第 555 趟车次由于停靠了 333 号火车站（222 级）却未停靠途经的 666 号火车站（亦为 222 级）而不满足要求。
现有 mmm 趟车次的运行情况（全部满足要求），试推算这n nn 个火车站至少分为几个不同的级别。
输入格式
第一行包含 222 个正整数 n,mn, mn,m，用一个空格隔开。
第 i+1i + 1i+1 行(1≤i≤m)(1 ≤ i ≤ m)(1≤i≤m)中，首先是一个正整数 si(2≤si≤n)s_i(2 ≤ s_i ≤ n)si(2≤si≤n)，表示第i ii 趟车次有 sis_isi 个停靠站；接下来有si s_isi个正整数，表示所有停靠站的编号，从小到大排列。每两个数之间用一个空格隔开。输入保证所有的车次都满足要求。
输出格式
一个正整数，即 nnn 个火车站最少划分的级别数。
输入输出样例
输入 #1
9 2 4 1 3 5 6 3 3 5 6
输出 #1
2
输入 #2
9 3 4 1 3 5 6 3 3 5 6 3 1 5 9
输出 #2
3
说明/提示
对于20% 的数据，1≤n,m≤10；
对于 50%的数据，1≤n,m≤100；
对于 100%的数据，1≤n,m≤1000。
分析；
刚开始还没有看懂题意，然后感觉暴力可以直接找到最大的车站等级，感觉可能是这样的，然后暴力写了两发都wa了，可能还是太菜没有领悟暴力大法的真谛，言归正传，这道题可以用拓扑排序做，每次停的车站都是要比没听的车站的等级高，那么建图的时候，就可以根据每一次未停靠的车站指向停靠的车站，虽然我感觉有点复杂，就不想打（for循环一用多，自动感觉复杂，还是太懒了）但是我还是硬着头皮打了下来，建图的时候要判断这条路径有没有已经被加过了，所以要开个二维数组记录记录一下，然后就是常规操作了。
代码：
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#include<queue>
#include<stack>
using namespace std;
struct zxc
{
int to,next;
}edge[1000005];
struct node
{
int id,v;
}s;
int f[1005][1005],a[1005],b[1005];
int rudu[1005];
int head[1005];
int cut=1,ans=0;
int n,m;
void add(int x,int y)
{
edge[cut].to=y;
edge[cut].next=head[x];
head[x]=cut;
cut++;
rudu[y]++;
}
int solve()
{
queue<node>q;
for(int i=1;i<=n;i++)
{
if(rudu[i]==0)
{
s.id=i;
s.v=1;
q.push(s);
}
}
node w,u;
while(!q.empty())
{
w=q.front();
q.pop();
ans=max(ans,w.v);
for(int i=head[w.id];i!=-1;i=edge[i].next)
{
rudu[edge[i].to]--;
if(rudu[edge[i].to]==0)
{
u.id=edge[i].to;
u.v=w.v+1;
q.push(u);
}
}
}
return ans;
}
int main()
{
memset(head,-1,sizeof(head));
memset(rudu,0,sizeof(rudu));
scanf("%d%d",&n,&m);
while(m--)
{
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
int k;
scanf("%d",&k);
for(int i=1;i<=k;i++)
{
scanf("%d",&a[i]);
b[a[i]]++;
}
for(int i=a[1];i<=a[k];i++)
{
if(b[i]==0)
{
for(int j=1;j<=k;j++)
{
if(f[i][a[j]]==0)
{
f[i][a[j]]=1;
add(i,a[j]);
}
}
}
}
}
printf("%d\n",solve());
return 0;
}
