傳送門
題目描述
一條單向的鐵路線上，依次有編号為 1, 2, …, n 1,2,…,n的 n n個火車站。每個火車站都有一個級别，最低為 11 級。現有若幹趟車次在這條線路上行駛，每一趟都滿足如下要求：如果這趟車次停靠了火車站 xx，則始發站、終點站之間所有級别大于等于火車站 xx 的都必須停靠。（注意：起始站和終點站自然也算作事先已知需要停靠的站點）
例如，下表是 5 5趟車次的運作情況。其中，前 44 趟車次均滿足要求，而第 55 趟車次由于停靠了 33 号火車站（22 級）卻未停靠途經的 66 号火車站（亦為 22 級）而不滿足要求。
現有 mm 趟車次的運作情況（全部滿足要求），試推算這 nn 個火車站至少分為幾個不同的級别。
輸入格式
第一行包含 22 個正整數 n, mn,m，用一個空格隔開。
第 i + 1i+1 行(1 ≤ i ≤ m)(1≤i≤m)中，首先是一個正整數 s_i(2 ≤ s_i ≤ n)s
i
(2≤s
i
≤n)，表示第 ii 趟車次有 s_is
i
個停靠站；接下來有 s_is
i
個正整數，表示所有停靠站的編号，從小到大排列。每兩個數之間用一個空格隔開。輸入保證所有的車次都滿足要求。
輸出格式
一個正整數，即 nn 個火車站最少劃分的級别數。
輸入輸出樣例
輸入 #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%20%的資料，1 ≤ n, m ≤ 101≤n,m≤10；
對于 50%50%的資料，1 ≤ n, m ≤ 1001≤n,m≤100；
對于 100%100%的資料，1 ≤ n, m ≤ 10001≤n,m≤1000。
希望各位看了這篇題解加知識講解之後能夠有隊拓撲排序有基本的運用,我會盡力寫得通俗易懂，這也是我一概的習慣
題解
0.寫在前面：
首先我們需要對拓撲排序有一個基本的認識
簡單的來說，拓撲排序就是将所有的任務按照先後順序進行排序，然後很友善地進行處理問題
下面是一道模闆題（UVA10305）：
題意翻譯
John有n個任務要做，每個任務在做之前要先做特定的一些任務。
輸入第一行包含兩個整數n和m，其中1<=n<=100。 n表示任務數，而m表示有m條任務之間
的關系。 接下來有m行，每行包含兩個整數i和j，表示任務i要在j之前做。
當讀入兩個0（i=0，j=0）時，輸入結束。
輸出包含q行，每行輸出一條可行的安排方案。
輸入 #1 複制
5 4
1 2
2 3
1 3
1 5
0 0
複制
輸出 #1 複制
1 4 2 5 3
輸出
1 4 2 5 3
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
const int N = 100 + 1;
int g[N][N];
int degreein[N];
int ans[N];
int n, m;
void toposort()
{
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
if(g[i][j])
degreein[j]++;//如果滿足拓撲的性質那麼，就讓指向的那個點++；
// 從節點号小的開始尋找
for(int i = 1; i <= n; i++) {
int k = 1;
while(degreein[k] != 0)
k++;//求對應的數
ans[i] = k;
degreein[k] = -1;
// 去除已經找出的節點的入度
for(int j = 1; j <= n; j++)
if(g[k][j])
degreein[j]--;
}
}
int main()
{
while(~scanf("%d%d", &n, &m) && (n || m)) {
// 初始化
memset(g, 0, sizeof(g));
memset(degreein, 0, sizeof(degreein));
memset(ans, 0, sizeof(ans));
// 讀入資料
int u, v;
for(int i = 1; i <= m; i++) {
scanf("%d%d", &u, &v);
g[u][v] = 1;
}
// 拓撲排序
toposort();
// 輸出結果
for(int i = 1; i < n; i++)
printf("%d ", ans[i]);
printf("%d\n", ans[n]);
}
return 0;
}
P1983
1.算法分析
（1）明顯的使用topu排序，将輸入資料與其補集進行連邊，并且連邊的時候，為了友善之後的周遊，順便求出每個數的出度
（2）然後，在求解的時候，大緻想法就是從出度為0的最低點開始掃，每次掃一層出度為0的點，ans++。
之後便将這一層的點與整個圖分離，分到最後出度為0的點求不出來的時候，就結束循環
2.片段代碼
1-（1）
cin>>n>>m;
for(int i=1;i<=m;i++)
{
memset(book,0,sizeof(book));//用來标記是否停靠該點
cin>>a;
for(int j=1;j<=a;j++)
{
cin>>h[j];
book[h[j]]=1;
}
for(int j=h[1];j<=h[a];j++)
{
if(!book[j])//如果沒有停靠，就将它和停靠了的所有點連上一條有向邊
{
for(int k=1;k<=a;k++)
{
if(!topu[j][h[k]])
{
topu[j][h[k]]=1;//指的是h[]指向j
du[h[k]]++;//求h[]的出度
}
}
}
}
}
2-（2）
int top=0;
do
{
top=0;
for(int i=1;i<=n;i++)
{
if(!yoyo[i]&&du[i]==0)
{
top++;
yoyo[i]=1;
stack1[top]=i;//用來存儲掃出的度為0的點
}
}
for(int i=1;i<=top;i++)
{
for(int j=1;j<=n;j++)
{
if(topu[stack1[i]][j])
{
topu[stack1[i]][j]=0;//去點去邊
du[j]--;
}
}
}
ans++;//這裡要注意，因為最後一次多了一個循環，是以在輸出時需要ans--；
}while(top);
3.附上AC代碼
#include<bits/stdc++.h>
#define maxn 10000
using namespace std;
int n,m;
int book[maxn];
int h[maxn];
int a;
int ans;
int yoyo[maxn],stack1[maxn];
int du[maxn];
int topu[1005][1005];
int main()
{
cin>>n>>m;
for(int i=1;i<=m;i++)
{
memset(book,0,sizeof(book));
cin>>a;
for(int j=1;j<=a;j++)
{
cin>>h[j];
book[h[j]]=1;
}
for(int j=h[1];j<=h[a];j++)
{
if(!book[j])
{
for(int k=1;k<=a;k++)
{
if(!topu[j][h[k]])
{
topu[j][h[k]]=1;
du[h[k]]++;
}
}
}
}
}
int top=0;
do
{
top=0;
for(int i=1;i<=n;i++)
{
if(!yoyo[i]&&du[i]==0)
{
top++;
yoyo[i]=1;
stack1[top]=i;
}
}
for(int i=1;i<=top;i++)
{
for(int j=1;j<=n;j++)
{
if(topu[stack1[i]][j])
{
topu[stack1[i]][j]=0;
du[j]--;
}
}
}
ans++;
}while(top);
cout<<ans-1<<endl;
while（1）
cout<<"Sabrina"<<endl;
return 0;
}
![[狀壓DP]【NOIP2016D2T3】憤怒的小鳥 題解[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)