前阵子准备某大厂OD机考C卷看到一道“主次关联成环警告”的双机位机考题。题面很长讲的是任务调度里的主次关联本质上就是给一张有向图判断里面有没有环。这题很适合拿来练手因为Java、Python、JS、Go、C、C都能写而且算法本身是图论里最基础的拓扑排序。准备机考的同学可以当模板记想巩固有向图环检测的朋友也能参考。我在第一次做这道题时第一反应是用并查集代码写得飞快样例也过了结果提交只对了一半。后来老老实实换成拓扑排序一次通过。今天就把这道题从题面拆到算法再到多语言实现完整聊一遍顺便把我在双机位考试环境下踩过的坑都整理出来。1. 题目场景与核心考点拆解1.1 题面到底在说什么题目会模拟一套任务调度系统。系统里有N个任务编号从1到N同时给M条主次关联关系。每条关系输入两个ID比如“a b”表示主任务a和次任务b之间存在关联。这个关联是有方向的一种常见理解是主任务a启动前必须等待次任务b完成另一种理解是主任务a执行时会触发次任务b。不管按哪种理解只要这些关联头尾相接形成一个循环就会出现“互相等待”或者“互相触发”的死结。举例来说任务1要等任务2任务2又要等任务1那谁都跑不完。题目要求你判断整个调度关系里是否存在这样的环如果存在就输出成环警告如果整张图无环就输出正常。很多第一次做题的同学看到“警告”两个字以为要写日志系统或者消息队列其实题目根本不关心业务层。它只问你一件事这张有向图有没有环。只要把业务包装剥掉考点就非常清晰了。1.2 从业务描述到图模型把每个任务看成一个节点把每条主次关联看成一条有向边题目就变成了标准的有向图环检测问题。节点的数量N和边的数量M通常都比较大常见数据规模能到10^5级别所以不能用暴搜把所有路径找一遍必须用O(NM)的算法。这里要特别强调“有向”两个字。有向图里判断环和无向图完全不是一回事。无向图里两个点只要连通就一定能从一边走到另一边有向图里边上带着方向从A能到B不代表从B能到A。很多同学第一次做这类题下意识用并查集就是没想清楚这个区别。建图方向也需要提前定好。我在下面的实现里统一约定主任务a依赖次任务b所以建边b → a也就是次任务先完成主任务后执行。拓扑排序时被依赖的一方先出队。如果题目给你的关联方向正好相反就把a和b的位置对调判环结论不会变影响的只是具体环节点的输出顺序。2. 算法选型Kahn排序是双机位机考的稳妥答案2.1 别用并查集碰有向图并查集适合无向图的连通性维护和环检测但拿到有向图里就会出现误判。最典型的反例三个节点1、2、3边为1→2、1→3、2→3。这张图没有环拓扑顺序就是1、2、3。但如果你用并查集按边的顺序依次合并集合处理到2→3时会发现2和3已经在同一个集合里于是误判成有环。原因也很简单并查集只记录“两个节点有没有连通”不记录“能不能沿着边的方向走回去”。有向图成环需要的是方向上的循环而不是单纯的连通。所以一看到“主次关联”这种有向关系就主动放弃并查集能省下大量排查时间。2.2 Kahn拓扑排序的原理与复杂度Kahn算法维护一个入度数组。入度为0的节点不依赖任何其他节点可以马上执行。算法的过程是先把所有入度为0的节点放进队列然后不断出队把出队节点的所有后继节点的入度减1如果某个后继的入度减到0就继续入队。最后统计一共处理了多少个节点。如果处理的数量等于N说明所有节点都能找到合理的执行顺序图中没有环。如果处理到一半队列就空了剩下节点入度都大于0说明它们之间存在循环等待也就是有成环。复杂度和空间都很干净。读入M条边是O(M)每个节点入队出队一次每条边被访问一次整体O(NM)。空间上需要邻接表存边入度数组和队列各存N个节点总空间O(NM)。在10^5这个规模下这个算法几乎没有压力。2.3 要不要输出成环路径Kahn算法最大的优点是稳定、非递归、不容易爆栈但它只能告诉你“有没有环”不能直接告诉你“环上有哪几个节点”。如果题目只是要求输出WarningKahn就是最合适的方案。如果题目要求把具体的环节点打印出来就需要换一种思路DFS三色标记法。DFS三色标记法把节点状态分成0未访问、1在当前访问栈中、2已访问完毕。当DFS从某个节点往下走遇到一个状态为1的节点说明栈中出现了回边从当前节点到栈中那个节点之间的所有节点就是环。这个方案可以输出环路径但递归深度较大的时候需要小心处理栈溢出。我的建议是先把Kahn版写熟再看DFS扩展。因为考试中大部分情况只需要返回值Kahn能覆盖绝大多数场景。3. 六语言核心实现与关键细节3.1 Java泛型数组与QueueJava实现里邻接表比较自然的写法是ListInteger[]。虽然不是完全类型安全但在考试环境中写起来快。队列用ArrayDeque不要用LinkedList后者虽然也能用但性能和代码观感都不如前者。import java.util.*; public class CycleWarning { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); int m sc.nextInt(); ListInteger[] graph new List[n 1]; for (int i 1; i n; i) { graph[i] new ArrayList(); } int[] indeg new int[n 1]; for (int i 0; i m; i) { int a sc.nextInt(); // 主任务 int b sc.nextInt(); // 次任务 graph[b].add(a); // 次任务先完成所以边从 b 指向 a indeg[a]; } QueueInteger q new ArrayDeque(); for (int i 1; i n; i) { if (indeg[i] 0) { q.offer(i); } } int cnt 0; while (!q.isEmpty()) { int u q.poll(); cnt; for (int v : graph[u]) { indeg[v]--; if (indeg[v] 0) { q.offer(v); } } } System.out.println(cnt n ? OK : Warning: cycle found); } }这里有一个容易忽略的点数组下标是从1开始的所以邻接表和入度数组都要开n 1否则编号为n的节点会越界。如果题目改成从0开始编号那就开大小为n的数组循环也从0到n-1。每次读题先确认编号起点能少交一次错误答案。Scanner在数据量达到10^5时一般够用但如果题目数据更猛可以考虑换成BufferedReader。核心逻辑不变只是读入方式换成按行解析这个属于锦上添花。3.2 Python快读和dequePython在机考里最大的优势是写起来快最大的隐患是输入慢和递归深。这道题用Kahn算法正好避开递归。输入方面不要用一行一次input()去循环读因为M一多就会明显变慢。更稳妥的方式是用sys.stdin.buffer.read()一次性读入全部数据再切分。import sys from collections import deque def solve(): data sys.stdin.buffer.read().split() it iter(data) n int(next(it)) m int(next(it)) graph [[] for _ in range(n 1)] indeg [0] * (n 1) for _ in range(m): a int(next(it)) b int(next(it)) graph[b].append(a) indeg[a] 1 q deque(i for i in range(1, n 1) if indeg[i] 0) cnt 0 while q: u q.popleft() cnt 1 for v in graph[u]: indeg[v] - 1 if indeg[v] 0: q.append(v) print(OK if cnt n else Warning: cycle found) if __name__ __main__: solve()Python的deque.popleft()是O(1)所以不用担心队列性能。用迭代器it iter(data)依次取值也比每次通过索引取值更简洁。要注意的是data里的元素都是bytes类型必须用int()转换漏了转换会出现类型错误。这个错误在本地可能不明显但在判题环境里会直接RE。3.3 JavaScript数组模拟队列JavaScript没有内置的队列结构。最直接的方案是用数组的shift()出队但shift()每次都会把后面的元素往前挪时间复杂度是O(n)在10^5的数据下会拖慢很多。正确的做法是用数组加头指针头指针一直向后走数组本身只负责追加元素。function solve(input) { const tokens input.trim().split(/\s/); let idx 0; const n tokens[idx]; const m tokens[idx]; const graph Array.from({ length: n 1 }, () []); const indeg new Array(n 1).fill(0); for (let i 0; i m; i) { const a tokens[idx]; const b tokens[idx]; graph[b].push(a); indeg[a]; } const q []; let head 0; for (let i 1; i n; i) { if (indeg[i] 0) q.push(i); } let cnt 0; while (head q.length) { const u q[head]; cnt; for (const v of graph[u]) { indeg[v]--; if (indeg[v] 0) q.push(v); } } console.log(cnt n ? OK : Warning: cycle found); }用tokens[idx]来快速转数字是JavaScript里常见的写法比parseInt少写几个字符。但要注意如果某个token是空字符串会得到0可能隐蔽地引入错误。所以读入时用trim()去掉首尾空白并用split(/\s/)切分连续空白基本能避免空串问题。在考试平台里输入可能以字符串形式传给solve也可能通过readline逐行给。把核心逻辑封装成solve(input)是比较稳的写法后续只要写一个读取外壳适配平台即可。3.4 Go切片当队列用Go语言里切片天然支持动态追加所以可以拿切片当队列。避免用container/list因为链表的节点分配开销大代码也没有切片直观。这里用head指针模拟出队出队只是把指针往后移并不真正删除元素内存上更友好。package main import ( bufio fmt os strconv strings ) func main() { sc : bufio.NewScanner(os.Stdin) sc.Buffer(make([]byte, 1024*1024), 1024*1024) sc.Scan() nm : strings.Fields(sc.Text()) n, _ : strconv.Atoi(nm[0]) m, _ : strconv.Atoi(nm[1]) graph : make([][]int, n1) indeg : make([]int, n1) for i : 1; i n; i { graph[i] []int{} } for i : 0; i m; i { sc.Scan() ab : strings.Fields(sc.Text()) a, _ : strconv.Atoi(ab[0]) b, _ : strconv.Atoi(ab[1]) graph[b] append(graph[b], a) indeg[a] } q : make([]int, 0, n) for i : 1; i n; i { if indeg[i] 0 { q append(q, i) } } cnt : 0 for head : 0; head len(q); head { u : q[head] cnt for _, v : range graph[u] { indeg[v]-- if indeg[v] 0 { q append(q, v) } } } if cnt n { fmt.Println(OK) } else { fmt.Println(Warning: cycle found) } }Go里最容易踩的坑是Scanner的默认行长度限制。如果某一行特别长sc.Scan()会返回false程序就静默结束了。所以必须先调用sc.Buffer扩大缓冲。另外strconv.Atoi会返回两个值考试时可以忽略错误但正式项目中不要忽略。开切片时预留cap为n可以减少扩容次数性能更好。3.5 Cvector与queueC写图论题最舒服的地方是STL直接提供了vector和queue代码量可以压缩得很短。这道题用vectorvectorint存邻接表就够了不需要手写链表。输入输出记得关掉同步否则数据量大时可能超时。#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin n m; vectorvectorint graph(n 1); vectorint indeg(n 1, 0); for (int i 0; i m; i) { int a, b; cin a b; graph[b].push_back(a); indeg[a]; } queueint q; for (int i 1; i n; i) { if (indeg[i] 0) q.push(i); } int cnt 0; while (!q.empty()) { int u q.front(); q.pop(); cnt; for (int v : graph[u]) { indeg[v]--; if (indeg[v] 0) q.push(v); } } cout (cnt n ? OK : Warning: cycle found) \n; return 0; }ios::sync_with_stdio(false); cin.tie(nullptr);这两行建议直接背下来几乎所有C机考题都能用上。vectorvectorint如果担心内存碎片可以提前reserve但在10^5量级一般不需要。这个实现里没有释放内存考试程序退出就回收了不用担心。3.6 C手写邻接表和队列C语言没有STL所有数据结构都要自己维护。用邻接表时我习惯每个节点维护一个链表用一个额外的tail指针指向链表尾部这样插入新边是O(1)。队列直接用数组和头尾下标模拟简单可靠。#include stdio.h #include stdlib.h #define MAXN 100005 typedef struct Node { int v; struct Node *next; } Node; Node *head[MAXN], *tail[MAXN]; int indeg[MAXN]; int q[MAXN]; void addEdge(int from, int to) { Node *nd (Node *)malloc(sizeof(Node)); nd-v to; nd-next NULL; if (tail[from] NULL) { head[from] tail[from] nd; } else { tail[from]-next nd; tail[from] nd; } } int main() { int n, m; scanf(%d%d, n, m); for (int i 1; i n; i) { head[i] tail[i] NULL; indeg[i] 0; } for (int i 0; i m; i) { int a, b; scanf(%d%d, a, b); addEdge(b, a); indeg[a]; } int qh 0, qt 0; for (int i 1; i n; i) { if (indeg[i] 0) { q[qt] i; } } int cnt 0; while (qh qt) { int u q[qh]; cnt; Node *p head[u]; while (p ! NULL) { int v p-v; indeg[v]--; if (indeg[v] 0) { q[qt] v; } p p-next; } } printf(%s\n, cnt n ? OK : Warning: cycle found); return 0; }这里的MAXN是写死的如果题目数据范围没给到10^5可以根据需要调大或改成动态分配。动态分配更严谨但考试时用固定数组写更快。C的malloc在考试场景不手动free问题不大判断环境会在进程结束后回收内存但如果在一组数据里多次建图就一定要记得释放否则内存会涨上去。4. 双机位考试环境下的实战避坑指南4.1 先画图再写码样例一定要自测双机位考试和平时在家刷题不太一样主摄像头对着脸副机位对着屏幕和手部基本没有机会临时翻笔记。这种情况下最忌讳看到题目就闷头敲代码。我自己的习惯是先在草稿纸上写下N、M的范围、编号起点、边的方向然后画一个小图模拟一遍Kahn算法的流程。这道题可以准备三组边界样例。第一组是无环的2 1 / 1 2输出OK。第二组是环2 2 / 1 2 / 2 1输出Warning。第三组是自环1 1 / 1 1一个任务自己关联自己也是环输出Warning。把这三个样例在脑子里跑一遍建图方向就不会弄反。4.2 六种语言的输入性能陷阱输入性能在数据量小时根本看不出来数据量一到10^5就容易卡住。整理一个速查表考试时可以直接对照。语言推荐读入方式需要避开的坑JavaBufferedReader 或 ScannerScanner在数据量大时偏慢能用Buffer就用BufferPythonsys.stdin.buffer.read().split()避免逐行input()避免忘记转intJavaScript一次读入后split(/\s/)不要用shift()模拟队列Gobufio.Scanner Buffer扩大不扩大Buffer长行会读不完Cios::sync_with_stdio(false)不关同步可能超时Cscanf固定数组注意MAXN要覆盖题目范围这些都是老生常谈但每个都真实坑过不少人。我见过Python交上去超时最后只是把input()改成sys.stdin.buffer.read()就AC的例子。4.3 时间分配和检查顺序三小时的机考建议花前五分钟确认题意和算法十分钟左右写完主逻辑再留三五分钟构造边界数据验证。不要急着提交哪怕样例全过也要再检查几个容易出现隐藏环的情况。检查顺序我习惯这样走一遍编号是1开始还是0开始数组有没有开大一位邻接表和入度方向是否一致循环有没有从1扫到n而不是从0扫到n-1最终判断是cnt n而不是cnt n - 1。这几处都是最容易手滑的地方。5. 常见问题与排查技巧实录5.1 并查集错在哪一个无环却被判环的例子我在开头说第一次用并查集只对了一半原因是它会把一些无环图误判成有环。这里把那个反例再展开一次方便以后避开。假设有3个节点关系是1→2、1→3、2→3。这个图明显无环因为1在最前面2和3都在它后面3又在2后面。并查集处理第一条边时合并1和2处理第二条边时合并1和3处理第三条边时发现2和3已经在同一集合里于是认为有环。这就是典型的误判。有向图判环必须依赖方向。Kahn算法里入度的增减天然体现方向只有当前置节点被处理完后继节点才会被释放。并查集没有这种机制所以不适合这道题。5.2 如何优雅地输出具体环路径如果题目从“判断是否有环”升级成“输出环上的节点”Kahn就不够用了。可以用DFS三色标记法状态1表示当前节点还在递归栈中遇到状态1的节点就说明找到了环。下面给一个Python版本做参考。import sys sys.setrecursionlimit(200000) def find_cycle(n, graph): state [0] * (n 1) # 0未访问1在栈中2已结束 stack [] def dfs(u): state[u] 1 stack.append(u) for v in graph[u]: if state[v] 0: if dfs(v): return True elif state[v] 1: idx stack.index(v) print(Warning:, *stack[idx:]) return True stack.pop() state[u] 2 return False for i in range(1, n 1): if state[i] 0 and dfs(i): return print(OK)这个版本里stack.index(v)是O(n)的查找只有在出现环时才会执行一次所以不影响整体复杂度。如果环很长可以用一个位置数组记录每个节点在栈中的下标把查找降到O(1)。但考试中这个版本已经够用。用Java或C写DFS时要注意递归深度建议改成显式栈或者直接用Kahn判环。5.3 邻接表方向不一致怎么办很多同学写完代码后发现样例能过但总担心方向反了。有个简单的验证方法造一条只有两个节点的边比如1 2。按b→a的建法2入度是01入度是1Kahn会先处理2再处理1无环输出OK。如果建图时不小心写成a→b同样这两个节点也不会产生环样例照样OK。所以容易漏掉。真正的方向问题在环节点输出时才明显。如果你只需要判环方向反了不影响结果。但如果你需要按期望顺序输出环节点就必须检查建边逻辑。最好的办法是在读入时写一行注释把“a依赖b所以b→a”写在代码旁边防止时间长了忘记。5.4 实战排查速查表现象可能原因排查方向数组越界编号从1开始但数组长度是n把数组开到n1大量超时输入太慢或队列实现差换快读避免shift()样例过但提交错并查集误判或有向方向建反换Kahn检查建边方向输出OK但有环判的环不是从所有节点出发检查循环是否遍历1到n全部节点递归爆栈用了DFS三色但递归太深换Kahn或调大递归限制这张表是我自己排查时常用的小抄。遇到问题先对着表看能省掉很多时间。6. 一点个人体会双机位机考和平常刷题最大的区别就是心态和节奏。我第一次踩了并查集的坑之后深刻理解了一个道理题目包装越花哨越要早一点剥出数据结构和算法本质。“主次关联成环警告”这个名字看着吓人核心就是有向图判环而Kahn拓扑排序是处理这类问题最稳的方案。如果你也在准备这类机考我建议把Kahn算法练到不用思考就能默写的程度同时把Java、Python、JS、Go、C、C这六种语言里的队列写法都过一遍。考试时不管选哪种语言核心逻辑都一样不同的只是语法细节。最后再分享一个小技巧考前一晚不要刷难题把这种常见模板题快速过一遍效果往往比临时抱佛脚要好得多。