洛谷P1983车站分级

洛谷\(P1983\)车站分级（拓扑排序）

---

目录

• 题目描述

• 题目分析

• 思路分析

• 代码实现

---

题目描述

题目在洛谷\(P1983\)上

​题目：

​输入输出格式：

---

题目分析

​刚刚看到这道题时，我并没有读懂题，觉得是要用一个\(dp\)或者搜索什么的（也有可能是我搜索题做多了

---

思路分析

​根据上面的题目分析，我们可以得出以下解题方法：

---

代码实现

#include<bits/stdc++.h>

using namespace std;

const int MAXN=3000010;

const int maxn=1005;

int head[MAXN],to[MAXN],nxt[MAXN];

int in[maxn],cnt,dep[maxn];

int a[maxn],flag[maxn],vis[maxn][maxn],ans;

//flag标记是否停靠，vis去重边

inline void add(int u,int v)

{

    cnt++;

    to[cnt]=v;

    nxt[cnt]=head[u];

    head[u]=cnt;

}//邻接链表存边

int n,m;

int main()

{

    scanf("%d%d",&n,&m);

    for(int i=1;i<=m;i++)

    {

        memset(a,0,sizeof(a));

        memset(flag,0,sizeof(flag));

        int k;

        scanf("%d",&k);

        for(int j=1;j<=k;j++)

        {

            scanf("%d",&a[j]);

            flag[a[j]]=1;//标记

        }

        for(int j=a[1]+1;j<=a[k];j++)

        {

            if(!flag[j])

            {

                for(int p=1;p<=k;p++)

                {

                    if(!vis[j][a[p]])

                    {

                        in[a[p]]++;

                        add(j,a[p]);

                        vis[j][a[p]]=1;

                    }

                }

            }

        }

    }

    queue<int> q;

    for(int i=1;i<=n;i++)

    {

        if(!in[i]) q.push(i),dep[i]=1;

        //刚开始入度就为0的点深度为1

    }

    while(!q.empty())

    {

        int top=q.front();

        q.pop();

        for(int e=head[top];e;e=nxt[e])

        {

            int v=to[e];

            dep[v]=max(dep[v],dep[top]+1);

            //这个不加max也可以，因为下面的ans已经取过max了

            //不过加上也没问题

            ans=max(ans,dep[v]);//更新答案

            in[to[e]]--;//入度--

            if(!in[to[e]]) q.push(to[e]);

        }

    }

    cout<<ans;

}

这是\(ych\)大神的代码（本蒟蒻表示还不会写）