拓扑入门之车站分级

题目链接；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

说明/提示

对于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;
}