---
# System prepended metadata

title: 2024/1/27 APCS 第一場模擬賽 題解
tags: [題解]

---

# 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))$ 個站著的人要下車，請你幫他計算，他能不能搶到座位。

保證捷運進站前所有人都會坐在座位上，但如果座位不夠就會有一些人是站著的。

![image](https://hackmd.io/_uploads/rJROh2as6.png)

![image](https://hackmd.io/_uploads/S1-chn6op.png)

![image](https://hackmd.io/_uploads/BJ65hhajp.png)

![image](https://hackmd.io/_uploads/rkzn2naip.png)

![image](https://hackmd.io/_uploads/rJyphhpsa.png)


### 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
![樹裡資優班 (Tree Gifted Class) 測資 1 範例圖](https://hackmd.io/_uploads/rJj6t69OT.png)
以下為範例 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")))
```
