# 2024/1/27 APCS 第一場模擬賽 題解
## 捷運 (Metro)
> 出題者：冰川
> 難度：p1
> 考點：輸入輸出、基本運算
### statement
冰川是一個非常愛搭捷運的人，每一次搭上捷運總是會忍不住一直在捷運上待到半夜，也因為這樣他總是很晚回家。但是，最讓他困擾的問題就是搶座位，雖然坐捷運很舒服，但要一直站著的話腳就會很酸。
為了更有效率地搶到座位，冰川很仔細的觀察每個乘客的行為。於是他發現每當捷運到站時，接下來的事情總是會依照順序發生：
- 需要下車的人會離開捷運
- 下車的人都離開之後，要是捷運上出現空位，附近的人就一定會馬上搶去坐下
- 等到捷運內沒有座位或所有乘客都坐下後，接下來新的一批乘客會排成一列上車，如果還有座位就會馬上搶著去座，且排在隊伍前面的人總是能比後面的人先搶到
這天，冰川一如往常的搶座位，他排在隊伍的第 $d(1 \le d \le 100)$ 個位置，而且他從窗外往內看時，看到車廂內共有 $n(1 \le n \le 100)$ 個座位和 $p(1 \le p \le 100)$ 個人，而在那 $p$ 人當中，有剛好 $m(0 \le m \le \min(p, n))$ 個坐在位子上的人要下車以及 $k(0 \le k \le \max(p - n, 0))$ 個站著的人要下車，請你幫他計算，他能不能搶到座位。
保證捷運進站前所有人都會坐在座位上，但如果座位不夠就會有一些人是站著的。
### Input
共有一行輸入，包含五個數字 $n$, $p$, $m$, $k$, $d$
### Output
如果有搶到座位就輸出 `Happy :>` 且在第二行輸出冰川坐下後還有多少空位
沒搶到就輸出 `Sad :((` 且在第二行輸出目前捷運內有幾個人站著（包含冰川）
### Testcase
- Input 1
```
5 7 4 1 2
```
- Output 1
```
Happy :>
1
```
- Input 2
```
5 7 4 1 5
```
- Output 2
```
Sad :((
2
```
### Subtask
- Subtask 1 (50%) - $d = 1$
- Subtask 2 (50%) - 無任何限制
### Note
- 第一筆測資模擬狀況跟示意圖一樣
### Solution
就直接模擬
數值加加減減這樣
### Code
- Subtask 1
```cpp
#include <bits/stdc++.h>
using namespace std;
int main() {
/* 輸出與初始化變數 */
int n, p, m, k, d;
cin >> n >> p >> m >> k >> d;
/* 初始狀態 */
int seats = max(n - p, 0); // 幾個空座位
int stand = max(p - n, 0); // 幾個人站著
/* 讓該下車的人下車 */
seats += m; // m 個坐著的人下車相當於增加 m 個空位
stand -= k; // k 個站著的人下車
/* 車內站著的人先搶座位 */
int tmp = seats - stand; // 站著的人都坐下後剩下多少座位 (負數代表座位不夠且有 tmp 個人站著)
seats = max(tmp, 0);
stand = max(-tmp, 0);
/* 放冰川進來搶座位 */
if (seats > 0) { // 還有座位
cout << "Happy :>" << endl; // 搶到了 ><
cout << seats - 1 << endl; // 被冰川搶走一個，所以剩下 seat - 1 個
} else {
cout << "Sad :((" << endl; // 沒搶到 qwq
cout << stand << endl; // 目前站著的人數
}
}
```
- Subtask 2
```cpp
#include <bits/stdc++.h>
using namespace std;
int main() {
/* 輸出與初始化變數 */
int n, p, m, k, d;
cin >> n >> p >> m >> k >> d;
/* 初始狀態 */
int seats = max(n - p, 0); // 幾個空座位
int stand = max(p - n, 0); // 幾個人站著
/* 讓該下車的人下車 */
seats += m; // m 個坐著的人下車相當於增加 m 個空位
stand -= k; // k 個站著的人下車
/* 車內站著的人先搶座位 */
int tmp = seats - stand;
seats = max(tmp, 0);
stand = max(-tmp, 0);
/* 放排在冰川前面的人進來搶座位 */
stand += max((d - 1) - seats, 0);
seats = max(seats - (d - 1), 0);
/* 放冰川進來搶座位 */
if (seats > 0) { // 還有座位
cout << "Happy :>" << endl; // 搶到了 ><
cout << seats - 1 << endl; // 被冰川搶走一個，所以剩下 seat - 1 個
} else {
cout << "Sad :((" << endl; // 沒搶到 qwq
cout << stand << endl; // 目前站著的人數
}
}
```
也可以參考 Guonuo 寫的超簡潔 AC code
```cpp
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, p, m, k, d;
cin >> n >> p >> m >> k >> d;
int g = n - (p - m - k + d - 1);
if (g > 0) cout << "Happy :>\n" << g-1 << endl;
else cout << "Sad :((\n" << (-g) << endl;
}
```
## 池塘 (Pond)
> 出題者：wym
> 難度：p2
> 考點：迴圈、陣列
### statement
現在有 $N$ 個池塘，每個池塘都和另外 $M$ 個池塘有通道連接，一開始每個池塘都有 $K$ 個魚，對於第 $i$ 個池塘，所有魚體積分別為 $v_{i,1}, v_{i, 2}, \dots , v_{i, K}$。
每一秒，都會有兩隻分別在第 $i, j$ 池塘、體積為 $v_{i, k}, v_{j, l}$ 的魚決定交換池塘，(如果他們所屬的池塘不相鄰，請告訴他們他們不能交換池塘，並不執行任何動作)，不幸的是，每個池塘都有自己能承受的魚體積總和上限，如果超過這個上限，這個池塘裡的魚就會集體憂鬱，不過一旦這個池塘裡的魚體積總和小於等於體積上限，所有魚就會變開心，對於每一秒，請計算出有幾隻憂鬱的魚。
### Input
第一行有五個數 $N, M, K, W, Q(2 \leq N \leq 20, \space 0 \leq M < N, \space 1 \leq K, Q \leq 20,\space 1 \leq W \leq 100)$ ，表示有 $N$ 個池塘、每個池塘有 $M$ 個通道、池塘中有 $K$ 隻魚、每個池塘體積上限是 $W$ 、經過 $Q$ 秒。
接下來 $N$ 行，每行有 $M$ 個數字代表與第 $i$ 個池塘有通道的池塘，一個池塘不會和自己有通道，通道是雙向的。
接下來 $N$ 行，每行有 $K$ 個數字代表第 $i$ 個池塘的$K$隻魚各自的體積，一隻魚的體積不超過 $100$。
接下來 $Q$ 行，每行有四個數字 $i,\space v_{i, k},\space j,\space v_{j, l}$，代表第 $i$ 個池塘，體積為 $v_{i, k}$ 的魚，以及第 $j$ 個池塘體積為 $v_{j, l}$ 的魚想交換池塘，保證 $i \neq j$ 、 $1 \leq i, j \leq N$ 且兩個池塘中都有各至少一隻魚符合體積描述。
所有數字都是整數、同一行的數字以空白鍵分隔。
### Output
對於每一秒，請先輸出兩隻魚是否能交換(可以輸出`YES`、不行輸出`NO`)，再輸出交換後所有池塘總共有幾隻憂鬱的魚。
### Testcase
- Input 1
```
4 2 3 50 5
4 2
1 3
2 4
3 1
10 25 20
5 5 30
10 10 15
10 10 10
2 30 3 10
1 10 3 15
3 30 4 10
1 25 4 30
1 10 4 10
```
- Output 1
```
YES 6
NO 6
YES 3
YES 3
YES 3
```
第1秒：
第2池的30和第3池的10交換
池塘變為
```
10 25 20
5 5 10
10 30 15
10 10 10
```
第1、3池的魚憂鬱
第2秒：
第1池的10和第3池的15交換，因為第1、3池中間沒有通道，魚不交換
第3秒：
第3池的30與第4池的10交換
```
10 25 20
5 5 10
10 10 15
30 10 10
```
第1池的魚憂鬱
第4秒：
第1池的25和第4池的30交換
```
10 30 20
5 5 10
10 10 15
25 10 10
```
第1池的魚憂鬱
第5秒：
第1池的10和第4池的10交換
```
10 30 20
5 5 10
10 10 15
25 10 10
```
第1池的魚憂鬱
### Subtask
- Subtask 1 (60%) - 魚不會想去沒有相鄰的池塘
- Subtask 2 (40%) - 無特殊限制
### Solution
- Subtask 1
使用陣列分別紀錄每個池塘所有魚的體積總和，每次詢問改變池塘體積，並看所有池塘有幾個體積大於$W$。
- Subtask 2
差不多，但是再多建一個`path`陣列，`path[i][j]=1`代表池塘$i$、$j$中間有通道，每次詢問再多確認兩者是否有通道。
### Code
```cpp=
#include <iostream>
int main()
{
int fish_volume[25] = {};
bool path[25][25] = {};
int n, m, k, w, q;
std::cin >> n >> m >> k >> w >> q;
for(int i=1, x; i<=n; i++)
{
for(int j=0; j<m; j++)
{
std::cin >> x;
path[i][x] = 1;
}
}
for(int i=1, x; i<=n; i++)
{
for(int j=0; j<k; j++)
{
std::cin >> x;
fish_volume[i] += x;
}
}
while(q--)
{
int one, v1, two, v2;
std::cin >> one >> v1 >> two >> v2;
if(path[one][two])
{
std::cout << "YES ";
fish_volume[one] = fish_volume[one] + v2 - v1;
fish_volume[two] = fish_volume[two] + v1 - v2;
}
else
{
std::cout << "NO ";
}
int ans = 0;
for(int i=1; i<=n; i++)
{
if(fish_volume[i] > w)
ans += k;
}
std::cout << ans << "\n";
}
}
```
```python=
n, m, k, w, q = map(int,input().split())
s = n + 5
path = [[False for i in range(s)] for j in range(s)]
for i in range(1, n+1):
now = list(map(int,input().split()))
for j in now:
path[i][j] = True
fish = [0] * s
for i in range(1, n+1):
now = list(map(int, input().split()))
for j in now:
fish[i] += j
for i in range(q):
one, v1, two, v2 = map(int,input().split())
if path[one][two]:
fish[one] = fish[one] - v1 + v2
fish[two] = fish[two] - v2 + v1
print("YES", end = " ")
else:
print("NO", end = " ")
ans = 0
for i in fish:
if i > w:
ans += k
print(ans)
```
## 樹裡資優班 (Tree Gifted Class)
> 出題者：Cheng
> 難度：p3
> 考點：字串分析、樹、二分搜、排序
### statement
小提醒：此題敘提到的「樹」皆為 「[樹](https://zh.wikipedia.org/zh-tw/%E6%A0%91_(%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84))」
Cheng 想要報考數理資優班，但是他報錯了，他報成樹裡資優班了呀！
但是報名費都付了，不考挺可惜的，
既然是樹裡資優班的考題，題目肯定是要跟樹有相關的，
但 Cheng 對於樹的觀念不太熟悉，
因為 Chung 是預言家，所以 Cheng 找 Chung 出了一道模擬試題給他
這是一道爬樹問題，
有一個機器人可以接收指令來爬樹，
機器人一開始會在根節點上，
經過一連串指令過後機器人會在哪個節點？
指令如下：
* $P$：走向父節點
* $Ci$：走向第 $i$ 小的子節點
* $R$：走向第一個比當前節點還要大的兄弟節點
* $L$：走向第一個比當前節點還要小的兄弟節點
(兄弟節點：對於樹上一點 $v$，若 $u$ 與 $v$ 有共同父節點則 $u,v$ 互為兄弟節點)
指令會由左而右的去執行
當然題目也是有可能出錯的，如果題目是錯的，請直接輸出機器人會停在錯的指令之前的最後一個節點並結束程式。
因為題目是按照樹的資料去出的，所以樹的資料絕不會出現錯誤，
~~這棵樹可能是聖誕樹、榕樹、樟樹等~~
但是指令有可能叫你去一個不存在的節點，那這樣指令就是錯的。
希望你能順利的幫助 Cheng 考上樹裡資優班 / 數理資優班 / 武陵科學班！
### Input
測資範圍：
* $1 \leq n \leq 10^5$
* 指令不超過 $10^5$ 個
* 指令字串長度不超過 $7 \times 10^5$ 個字元
* $Ci$ 指令中 $1 \leq i \leq n$
* 保證輸入的資料可構成一棵樹
輸入共有 $n + 2$ 行
第一行有一個數字 $n$，代表有 $n$ 個節點
接下來有 $n$ 行，
每一行皆有 $k + 1$ 個數字，
第 $i$ 行第一個數字為 $k$ 代表有 $k$ 個點以 $i$ 節點當作父節點，
接下來 $k$ 個數字代表該節點的父節點為 $i$
接下來有一字串 $s$，代表所做的指令
### Output
輸出一個數字代表經過指令後機器人所到達的節點
### Testcase
- Input 1 (Sample)
```
7
2 2 3
2 4 5
2 6 7
0
0
0
0
C1RC2LPL
```
- Output 1 (Sample)
```
2
```
### Subtask
- Subtask 1 (10%) - 樹為一條鏈，並且題目不會出錯
- Subtask 2 (10%) - 樹為一條鏈，題目可能出錯
- Subtask 3 (20%) - 題目不會出錯
- Subtask 4 (60%) - 無其他限制
### Note
以下為範例 1 的說明：
根節點為 1
1. 經過 C1 指令後到達節點 2
2. 經過 R 指令後到達節點 3
3. 經過 C2 指令後到達節點 7
4. 經過 L 指令後到達節點 6
5. 經過 P 指令後到達節點 3
6. 經過 L 指令後到達節點 2
### Solution
- Subtask 1 (10%)
如果找到了一個點並沒有父節點，則該點為根節點，
會發現在鏈的情況下不能夠去做 $L$ 和 $R$ 的指令，所以該子題不會出現這兩種指令
並且 $Ci$ 指令中的 $i$ 必定為 1，因為鏈上任一節點一定只能指向一個以下的節點
小知識：發現只有 1 節點只能輸出 1 的話可以多撈 5 分
- Subtask 2 (10%)
遇 $L$、$R$ 指令則該指令必為錯誤指令
如果到了根節點使用 $P$ 指令為錯誤指令
如果到了鏈的尾端使用 $Ci$ 指令為錯誤指令
- Subtask 3 (20%)
指令使用時記得把某節點所指向的節點做 sort
以下稱排序後的序列為 $S$
遇到 $Ci$ 時走到 $Si$
遇到 $L$、$R$ 指令時
對父節點的 $S$ 二分搜找到第一個比自己大、比自己小的節點
(C++ 使用者可以使用 lower_bound 和 upper_bound 函式)
- Subtask 4 (60%)
遇 $Ci$ 指令時注意 $S$ 序列中的元素數量是否在 $i$ 以上
如否，則為錯誤指令
遇 $L$ 時須注意二分搜到的節點是否為 $S$ 中第一個元素
如是，則為錯誤指令
遇 $R$ 時須注意二分搜到的節點是否為 $S$ 中最後一個元素
如是，則為錯誤指令
遇 $P$ 時須注意目前所在的點是否為根節點
如是，則為錯誤指令
### Fun Fact
這題原本應該要更難的 QQ
原本的指令還有一個括號指令，括號內的指令會優先執行
但被 Chung 說太複雜就被砍了
我好難過
請大家去跟 Chung 抗議說這題太簡單沒難度
### Code
```cpp=
#include <bits/stdc++.h>
//#define int long long //TLE or MLE remove
#define F first
#define S second
#define Cheng0928 ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define SIZE(a) signed(a.size())
#define rALL(x) x.rbegin(), x.rend()
#define ALL(x) x.begin(), x.end()
#define PB push_back
#define MP make_pair
using namespace std;
const int MN = 5e7;
const int INF = 9e18;
const int MOD = 1e9 + 7;
void sol(){
int n;
cin >> n;
vector<vector<int>> c(n + 1);
vector<int> p(n + 1, 0);
for(int i = 1; i <= n; i++){
int k;
cin >> k;
int x;
for(int j = 1; j <= k; j++) cin >> x, c[i].PB(x), p[x] = i;
sort(ALL(c[i]));
}
int now;
for(int i = 1; i <= n; i++){
if(!p[i]){
now = i;
break;
}
}
string s;
cin >> s;
stringstream ss;
ss.str(s);
char o;
while(ss >> o){
if(o == 'C'){
int i;
ss >> i;
if(i > SIZE(c[now])){
cout << now << '\n';
return;
}
else{
now = c[now][i - 1];
}
}
else if(o == 'P'){
if(!p[now]){
cout << now << '\n';
return;
}
else{
now = p[now];
}
}
else{
if(!p[now]){
cout << now << '\n';
return;
}
int x;
if(o == 'L'){
auto it = lower_bound(ALL(c[p[now]]), now);
if(it == c[p[now]].begin()){
cout << now << '\n';
return;
}
x = prev(it) - c[p[now]].begin();
}
else{
auto it = upper_bound(ALL(c[p[now]]), now);
if(it == c[p[now]].end()){
cout << now << '\n';
return;
}
x = it - c[p[now]].begin();
}
now = c[p[now]][x];
}
}
cout << now << '\n';
}
signed main()
{
Cheng0928
int t;
t = 1;
//cin >> t;
//string ss;
//getline(cin, ss);
//init();
while(t--) sol();
return 0;
}
```
```python=
print((lambda n:(lambda con,s,l,r,p:sum(bool(p.__setitem__(j,i)) for i in range(n) for j in con[i]) or sum(bool(l.__setitem__(o[i+1],o[i]))+bool(r.__setitem__(o[i],o[i+1])) for o in con for i in range(len(o)-1)) or (lambda v,d:sum(bool(v.__setitem__(2,(con[v[0]][int(idx)-1] if len(con[v[0]])>=int(idx)>0 else -1) if idx else d[tp][v[0]]))+(bool(v.__setitem__(1,False)) if v[2]==-1 else bool(v.__setitem__(0,v[2]))) for tp, idx in __import__("re").findall("([PLRC])(\d+)?",s) if v[1]) or v[0]+1)([next(i for i in range(n) if p[i]==-1),True,-1],{"P":p,"L":l,"R":r}))([sorted([int(i)-1 for i in input().split()][1:]) for _ in range(n)],input(),[-1]*n,[-1]*n,[-1]*n))(int(input())))
```
## 排隊 (Queue)
> 出題者：Chung
> 難度：p4
> 考點：拓撲排序、資料結構
### statement
班上有 $n$ 個小朋友要排隊，為了讓小朋友們開心，老師允許每個小朋友列出願望清單，寫出想要有誰站在他的前面 (願望清單裡可以不只一個人，有可能出現重複的人，但不會出現自己)。
但有時候未必能如大家所願，因此老師希望你可以幫忙寫一個程式來分配隊伍，對於每個小朋友，他的願望清單裡的所有人都要排在他的前面，才算滿足條件。
為了更好的控管學生，老師希望可以獲得字典序最小的合法排隊方案，請輸出字典序最小的合法排隊方案 (保證至少存在一種合法的排隊方案)。
### Input
輸入第一行將有一個整數 $n(1 \leq n \leq 10^5)$，代表小朋友的數量，接下來會有 $n$ 行，第 $i$ 行的第一個數字為 $m_i(0 \leq m_i \leq n-1)$，代表願望清單裡有幾個人，緊接著就是 $m_i$ 個介於 $1 \sim n$ 的整數代表朋友的編號 $a_{i,1},a_{i,2},\dots,a_{i,m_i}。 (\sum_{i=1}^{n}m_i \leq 2 \times 10^5)$。
### Output
請輸出 $n$ 個數字 $ans_1 \space ans_2 \space \dots \space ans_n$，代表字典序最小的排隊方案。
### Input Format
$n$
$m_1 \space a_{1,1} \space a_{1,2} \space \dots \space a_{1,m_1}$
$m_2 \space a_{2,1} \space a_{2,2} \space \dots \space a_{2,m_2}$
$\dots$
$m_n \space a_{n,1} \space a_{n,2} \space \dots \space a_{n,m_n}$
### Output Format
$ans_1 \space ans_2 \space \dots \space ans_n$
### Testcase
- Input 1
```
5
1 3
1 1
0
0
1 4
```
- Output 1
```
3 1 2 4 5
```
### Subtask
- Subtask 1 (20%)：$n \leq 8$
- Subtask 2 (30%)：保證只會有一種合法的排隊方案
- Subtask 3 (50%)：無其他限制
### Solution
- Subtask 1
- 從 $1 \dots n$ 開始排列枚舉各種可能的排隊方案
- 對於每種排列進行檢查
- 只要清單裡面有人排在後面，表示不符合條件
- 預處理每個人的 index (所在位置)
- 枚舉所有人的所有清單，透過預處理可以 $O(1)$ 判斷任兩人誰前誰後 (比較 index)，因此檢查一個人的複雜度為 $O(m_i)$
- 檢查所有人總時間複雜度為 $O(nm_i)$
- 假如序列完全滿足條件，則必為字典序最小的解，直接輸出並結束程式即可
- 時間複雜度：$O(n! \space \times \space nm_i)$
- 如果沒有做預處理的話，複雜度會多乘上一個 $n$，但我沒有卡 $O(n! \space \times \space n^2m_i)$ 的這個作法，所以沒預處理還是可以拿到 20 分 XD
- Subtask 2
- 觀察到題目要求的其實就是拓撲排序
- 因為保證只有一種排隊方案，所以考慮最一般的拓撲排序
- 時間複雜度：令 $M = \sum_{i=1}^{n}m_i$ ，時間複雜度為 $O(n + M)$
- Subtask 3
- 使用 Kahn's Algorithm 演算法，並將 queue 改成使用 priority_queue (Python 可使用 heapq)
- 時間複雜度：令 $M = \sum_{i=1}^{n}m_i$，時間複雜度為 $O(nlogn + M)$
### Code
- Subtask 1 (C++)
```cpp=
#include<bits/stdc++.h>
#define int long long
#define f first
#define s second
#define fastio ios_base::sync_with_stdio(0);cin.tie(0)
using namespace std;
//declare
const int maxn = 9;
int n;
vector<int> v[maxn];
//
signed main(){
fastio;
cin>>n;
for(int i=1;i<=n;i++){
int m; cin>>m;
for(int j=0;j<m;j++){
int x; cin>>x;
v[i].push_back(x);
}
}
vector<int> ans(n);
iota(ans.begin(),ans.end(),1);
do{
vector<int> idx(n+1);
for(int i=0;i<n;i++) idx[ans[i]] = i;
bool flag = 1;
for(int i=1;i<=n;i++){
for(int j:v[i]){
if(idx[j] > idx[i]) flag = 0;
}
}
if(flag){
for(int i=0;i<n;i++){
cout<<ans[i];
if(i == n-1) cout<<"\n";
else cout<<" ";
}
return 0;
}
}while(next_permutation(ans.begin(),ans.end()));
return 0;
}
```
- Subtask 2 (C++)
```cpp=
#include<bits/stdc++.h>
#define int long long
#define f first
#define s second
#define fastio ios_base::sync_with_stdio(0);cin.tie(0)
using namespace std;
//declare
const int maxn = 1e5+5;
int t,n,in[maxn];
bool vis[maxn];
vector<int> G[maxn],ans;
//
void topo_sort(){
queue<int> q;
for(int i=1;i<=n;i++) if(in[i] == 0) q.push(i);
while(!q.empty()){
int cur = q.front(); q.pop();
ans.push_back(cur);
for(int adj : G[cur]){
if(--in[adj] == 0) q.push(adj);
}
}
}
signed main(){
fastio;
cin>>n;
for(int i=1;i<=n;i++){
int m; cin>>m;
for(int j=0;j<m;j++){
int x; cin>>x;
G[x].push_back(i);
in[i]++;
}
}
topo_sort();
for(int i=0;i<n;i++){
cout<<ans[i]<<" \n"[i == n-1];
}
return 0;
}
```
- Subtask 2 (Python)
```python=
from queue import Queue
n = int(input())
in_degree = [0]*(n+1)
G = [list() for _ in range(n+1)]
# 進行拓撲排序，將結果存在 result
q = Queue()
result = []
def topo_sort():
for i in range(1, n+1):
if in_degree[i] == 0:
q.put(i)
while not q.empty():
cur = q.get()
result.append(cur)
for child in G[cur]:
in_degree[child] -= 1
if in_degree[child] == 0:
q.put(child)
# 建圖
for i in range(1, n+1):
a = list(map(int,input().split()))
k = a[0]
for j in range(1, len(a)):
G[a[j]].append(i)
in_degree[i] += 1
# 呼叫拓撲排序並輸出結果
topo_sort()
print(*result)
```
- Subtask 3 (C++)
```cpp=
#include<bits/stdc++.h>
#define int long long
#define f first
#define s second
#define fastio ios_base::sync_with_stdio(0);cin.tie(0)
using namespace std;
//declare
const int maxn = 1e5+5;
int t,n,in[maxn];
bool vis[maxn];
vector<int> G[maxn],ans;
//
void topo_sort(){
priority_queue<int,vector<int>,greater<int>> q;
for(int i=1;i<=n;i++) if(in[i] == 0) q.push(i);
while(!q.empty()){
int cur = q.top(); q.pop();
ans.push_back(cur);
for(int adj : G[cur]){
if(--in[adj] == 0) q.push(adj);
}
}
}
signed main(){
fastio;
cin>>n;
for(int i=1;i<=n;i++){
int m; cin>>m;
for(int j=0;j<m;j++){
int x; cin>>x;
G[x].push_back(i);
in[i]++;
}
}
topo_sort();
for(int i=0;i<n;i++){
cout<<ans[i]<<" \n"[i == n-1];
}
return 0;
}
```
- Subtask 3 (Python)
```python=
from heapq import heappush, heappop
n = int(input())
in_degree = [0]*(n+1)
G = [list() for _ in range(n+1)]
# 進行拓撲排序，將結果存在 result
pq = []
result = []
def topo_sort():
for i in range(1, n+1):
if in_degree[i] == 0:
heappush(pq, i)
while len(pq) > 0:
cur = heappop(pq)
result.append(cur)
for child in G[cur]:
in_degree[child] -= 1
if in_degree[child] == 0:
heappush(pq, child)
# 建圖
for i in range(1, n+1):
a = list(map(int,input().split()))
k = a[0]
for j in range(1, len(a)):
G[a[j]].append(i)
in_degree[i] += 1
# 呼叫拓撲排序並輸出結果
topo_sort()
print(*result)
```
- Subtask 3 (Python 一行解 by 橘子)
```python=
print(*(lambda n,pq:(lambda pre,nxt,ans,q,p:sum(bool(nxt[j].append(i)) for i in range(n) for j in pre[i]) or sum(bool(p.append(len(o))) for o in pre) or sum(p[i]==0 and bool(pq.heappush(q,i)) for i in range(n)) or sum(bool(ans.append(pq.heappop(q)+1))+sum(bool(p.__setitem__(j,p[j]-1))+(p[j]==0 and bool(pq.heappush(q,j))) for j in nxt[ans[-1]-1]) for _ in range(n)) or ans)([[int(i)-1 for i in input().split()][1:] for _ in range(n)],[[] for _ in range(n)],[],[],[]))(int(input()),__import__("heapq")))
```
Sign in with Wallet
Connect another wallet