問題描述

N 個成員（N≤100），M 對師徒關系（M≤100），x y 表示 x 是 y 的師父。關系具有傳遞性。若存在循環（A 是 B 師父且 B 是 A 師父），則不合法。對每個測試案例輸出 YES/NO。

解題思路

建立有向圖：x -> y 表示 x 是 y 師父。合法 ⇔ 圖中無環 ⇔ 存在拓撲序。用 Kahn 算法（BFS 拓撲排序）檢測環。

Kahn 算法流程

1. 計算所有節點入度。
2. 將入度為 0 的節點入隊。
3. 重複：出隊節點 u，計數 cnt++；遍歷 u 的出邊 u->v，in[v]--，若 in[v]==0 入隊。
4. 若 cnt == N，無環（YES）；否則有環（NO）。

代碼實現

#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;

const int MAXN = 105;
vector g[MAXN];
int in[MAXN];

int main() {
    int n, m;
    while (~scanf("%d%d", &n, &m) && n) {
        for (int i=0;i q;
        for (int i=0;i

關鍵細節

多測試用例：以 n=0 結束，每案例清空圖與入度。
重邊處理：題目未保證無重邊，重複邊會導致入度重複計數。用 bool g[MAXN][MAXN] 去重或輸入時檢查。
節點編號：0~N-1，直接作數組索引。
傳遞性：拓撲排序天然處理傳遞閉包，無需額外 Floyd/Warshall。


複雜度

時間：O(N + M) 每案例，極快。
空間：O(N + M)。


總結
HDU 3342 是拓撲排序判環的直接應用。師徒關系構成偏序集，合法性等價於無環。Kahn 算法代碼簡短、直觀，利用入度為 0 的節點作為「無前驅」的源頭，逐層剝離。若最終剝離節點數 < N，說明存在環（所有節點入度均 > 0）。掌握此模板，所有「依賴關系合法性/執行順序」問題通用。