【題目敘述】https://zerojudge.tw/ShowProblem?problemid=b333
【解題想法】拓撲排序 (Topological sorting)
- 第6筆測資一直無法通過。移除重複的邊後就AC了。測資中可能有大量重複的邊，會爆記憶體。
- vector<int> train：紀錄每一條路線停車的車站。
- 陣列 nxt[ ][ ]：紀錄是否有重複的邊。
- 陣列 in[ ]：紀錄比該車站級別低的車站數目。
- 陣列 lvl[ ]：紀錄每個車站的級別。
- 利用 in[ ], nxt[ ][ ]，建立DAG，接著是標準拓撲排序做法。
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
const int maxn = 1005;
int n, m, in[maxn], lvl[maxn], now, a, b, num, ans;
int nxt[1005][1005];
vector <int> train;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
memset(in, 0, sizeof(in));
memset(lvl, 0, sizeof(lvl));
memset(nxt, 0, sizeof(nxt));
for (int i = 0; i < m; i++){
train.clear();
cin >> num;
while (num--){
cin >> a;
a--;
train.push_back(a);
}
for (int i = train[0]+1; i < a; i++){
if (*lower_bound(train.begin(), train.end(), i) != i){
for (int j:train){
if (nxt[j][i] == 0){
nxt[j][i] = 1;
in[i]++;
}
}
}
}
}
queue <int> q;
for (int i = 0; i < n; i++){
if (in[i] == 0){
q.push(i);
lvl[i] = 1;
}
}
while (!q.empty()){
now = q.front();
q.pop();
for (int i = 0; i < n; i++){
if (nxt[now][i] == 0) continue;
in[i]--;
lvl[i] = max(lvl[i], lvl[now]+1);
if (in[i] == 0) q.push(i);
}
}
ans = 0;
for (int i = 0; i < n; i++){
ans = max(ans, lvl[i]);
}
cout << ans << "\n";
}