★ FEATURED ARTICLE 每年到OD刷题季总能看到不少人盯着主次关联成环警告这个题目名发懵主次关联是什么环是什么警告又是什么其实这道题背后是一个特别常见的业务场景——采购申请单管理系统里一张单可以被别的单引用为主单也可以引用别的单作为自己的主单这种主单-次单的引用关系一旦绕成一个圈审批流就会卡死系统必须把环找出来并发警告。这道题是华为OD机试双机位C卷的真题考点非常明确有向图判环。难度不高但坑不少尤其是输入输出格式、环路径输出的顺序、还有不同语言的提交细节。我下面用Java和Go各写一版完整实现把算法思路、边界条件和考场上的易错点全部摊开讲准备考C卷的可以直接参考。1. 主次关联的业务场景一张申请单为什么会把自己绕进环里1.1 采购申请单的主单-次单引用模型先说清楚题目里的主次关联到底是什么。在很多企业的采购、OA、审批系统里一张采购申请单可以因为金额过大、品类复杂等原因被拆成多张子单这些子单需要挂到一张主单下面反过来一张新单子也可能被已有的大单引用为附件或者补充材料。系统里就把这种谁被谁引用的关系称为主次关联。具体到数据结构上你可以把每一张申请单当成一个节点把次单指向主单或者子单指向父单当成一条有向边。这样整个主次关联关系就变成了一张有向图。正常情况下这张图应该是一棵或多棵有向树每个次单只有唯一的主单从任意节点沿着引用方向往上走最终会走到一个没有上级的主单。但这套逻辑在人工维护时特别容易出错。业务人员录单时手滑把编号填反、Excel批量导入时单元格串行、系统迁移时主外键映射错位都可能导致A引用B、B引用C、C又回过头来引用A的情况。一旦出现这种循环引用钱和物料就会在审批流里无限打转任何依赖顺着引用链路逐级汇总的功能都会当场崩溃。1.2 成环之后的真实后果很多不熟悉业务的开发同学拿到这道题会想不就是判个环吗图论模板题而已。但如果真在采购系统里出过故障你就知道这个小问题的杀伤力有多大。举一个真实场景采购金额需要按主单维度汇总如果某张次单的引用链路成环那么汇总逻辑会不停地在环里循环累加轻则单次查询超时重则把汇总线程池全部占满最后拖垮整个审批服务。再比如审批流引擎它会沿着主单往上找下一级审批人如果链路成环审批任务永远找不到终点这条单据就会一直卡在审批中业务人员催单时查不出来原因最后只能人肉清数据。这就是为什么题目要在判环之后输出警告而不是直接忽略这些脏数据。算法题并不总是高高在上的抽象题目很多时候就是从这类生产事故里提炼出来的。理解了这一点你就知道题目要求的不只是判断有没有环还要尽量把环的路径输出出来方便业务方去修数据。1.3 把业务问题翻译成图论问题把业务术语翻译成算法语言题目就一句话给定N个节点和M条有向边次单-主单判断这张有向图是否存在环如果存在输出环上经过的所有节点编号。业务名词图论概念申请单编号节点次单引用了主单有向边次单指向主单关联引用关系有向图循环引用有向环输出成环警告输出环路径做题时不需要真的理解业务但搞清楚边的方向非常重要。很多同学在考场上把方向读反建图建错了后面算法再对也白搭。建议在读题时先圈出谁指向谁这几个字如果题目说每行两个编号a b表示b是a的主单那就在代码里写graph.get(a).add(b)也就是a指向b。2. 输入格式与边界条件先把样例吃透再动笔2.1 标准输入约定与一个手推样例华为OD机试的输入一般是ACM模式也就是需要自己写main函数从标准输入读数据。这道题我按常见的格式来约定第一行两个整数N和M表示有N个申请单、M条关联关系接下来的M行每行两个整数from和to表示from节点引用了to节点作为主单。下面给一个能手动推演完整个流程的样例5 5 1 2 2 3 3 1 3 4 4 5先画一下图1-22-33-1这三条边构成了一个明显的环1到2到3再回到1所以整张图存在环输出应为有环警告: 1-2-3-1节点4和5虽然作为链的末端挂在那里但环已经存在了整张图不合法直接返回警告即可。2.2 自环、重边、孤立节点这类隐蔽边界做题只看样例是绝对不够的。我见过太多人样例过了、提交零分的情况基本都是边界条件没处理。这里我把这类题最常踩的几个边界情况列出来首先是自环也就是输入中出现1 1这样一条边。节点引用自己作为主单这本身就是合法的循环依赖必须判为有环。DFS的三色标记天然能处理自环访问节点1时把它标记为灰色遍历它的邻居时发现邻居1也是灰色立刻就能识别出环路径输出为1-1。其次是重边也就是1 2出现了两次。对判环逻辑来说重边不构成影响因为第二次访问2时它已经是黑色已完成访问直接跳过即可。但重边可能影响某些实现方式的运行效率用邻接表存储时最多多一条冗余数据问题不大。再就是孤立节点。有些申请单没有挂在任何主单下自己也没有次单这种节点在图中表现为没有边。判环时只需要对每个节点都做一次DFS入口判断孤立节点进去一趟、标记为黑色就出来了完全不干扰整体判断。最后是N比较大的情况。如果N到达10^5级别递归DFS要小心栈溢出。Java的虚拟机栈默认深度大概几千到一万Go的协程栈虽然是动态增长的但深递归仍然不够保险。这时候就要想办法改成显式栈的迭代写法或者用下面要讲的Kahn拓扑排序来规避递归深度问题。3. 环检测算法选型为什么普通visited数组会误判3.1 两色visited的经典翻车现场很多第一次接触判环题目的同学会写一个看起来很合理的DFS用一个boolean数组标记某个节点是否访问过然后在DFS里遇到已经访问过的节点就认为存在环。这个写法对有向图的环检测来说是错的。为什么会错看这个例子1-21-32-3一共三个节点三条边。如果用两色visited并按从1开始的顺序DFS访问顺序是进入1访问22没有邻居结束访问33没有邻居结束。整个过程中永远不会遇到访问到已经访问过的节点结果正确。但换个顺序1-21-33-2DFS顺序是进入1、访问2、结束、访问3、3的邻居是2此时2已经被标记为访问过于是程序误判为有环。但实际上这个图并没有环只是两条路径都汇到了节点2而已。两色visited的问题在于它把曾经访问过和当前递归路径上正在访问混为一谈后者才是判断环的真正依据。3.2 DFS三色标记的核心思路解决这个问题需要用三色标记法这也是有向图判环的标准写法。每个节点有三种颜色状态白色表示从未访问过灰色表示当前递归栈中正在访问黑色表示已经访问完毕、从该节点出发的所有路径都检查完了没有发现环。DFS遍历时每进入一个节点就把它置为灰色然后遍历它的邻居。如果遇到灰色邻居说明沿着当前路径一路走过来又绕回了路径上的某个节点环出现了。如果遇到黑色邻居说明从该邻居出发的子树已经验证无环可以直接跳过。当前节点的所有邻居都遍历完后把它置为黑色返回上一层。这样就能区分3.1里的两种情况节点2虽然在某个分支里被访问过但访问完成后它已经是黑色从节点3再遇到它时它不在当前递归栈中就不构成环。颜色标记本质上记录的是这个节点和当前递归路径的关系而不是简单的见没见过。3.3 Kahn拓扑排序与三色标记的取舍除了DFS三色标记判断有向图是否有环另一个经典做法是Kahn拓扑排序。思想很简单不断把入度为0的节点从图中移除每移除一个节点就把它的出边指向的节点入度减1如果最终能移除的节点数等于总节点数N说明图无环否则说明存在环。Kahn的优点是天然迭代、不依赖递归N再大也不会栈溢出而且代码写起来比DFS三色标记还要短。但它的短板在于只能告诉你有没有环不能方便地提取出环的具体路径因为拓扑排序过程中被移除的都是非环节点剩下的节点都是环上的但环的顺序需要额外还原。回到这道题题目叫主次关联成环警告明确要求输出警告和环路径所以我会优先选择DFS三色标记。如果偶尔遇到N大到递归栈实在顶不住可以先把环上的节点找出来再反推顺序。下面给一个两种方法的功能对比对比项DFS三色标记Kahn拓扑排序判断是否有环支持支持输出环的具体路径可以直接回溯输出需要额外还原递归栈溢出风险有可用显式栈规避无天然迭代对自环的支持天然支持天然支持自环节点入度非0如果题目要求只是判断合法性不要求输出路径用Kahn会稳一点这道题既然点名要警告我建议直接按DFS三色标记写。4. Java实现邻接表建图与环路径回溯4.1 完整代码ACM模式可直接提交下面这版Java代码是完整的ACM模式类名为Main没有package声明提交到OD机试系统可以直接运行。关键逻辑在DFS里用颜色数组区分状态用prev数组记录每个节点的前驱环路径通过不断回溯前驱得到。import java.util.*; public class Main { static ListListInteger graph; static int[] color; // 0-白 1-灰 2-黑 static int[] prev; // 记录DFS树上的前驱节点 static ListInteger cyclePath; public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); int m sc.nextInt(); graph new ArrayList(n 1); color new int[n 1]; prev new int[n 1]; cyclePath new ArrayList(); Arrays.fill(prev, -1); for (int i 0; i n; i) { graph.add(new ArrayList()); } for (int i 0; i m; i) { int from sc.nextInt(); int to sc.nextInt(); graph.get(from).add(to); // from指向to } for (int i 1; i n; i) { if (color[i] 0 dfs(i)) { System.out.print(有环警告: ); for (int j 0; j cyclePath.size(); j) { if (j 0) System.out.print(-); System.out.print(cyclePath.get(j)); } System.out.println(); return; } } System.out.println(无环主次关联关系合法); } static boolean dfs(int u) { color[u] 1; for (int v : graph.get(u)) { if (color[v] 1) { cyclePath.clear(); int cur u; while (cur ! v) { cyclePath.add(cur); cur prev[cur]; } cyclePath.add(v); Collections.reverse(cyclePath); cyclePath.add(v); return true; } if (color[v] 0) { prev[v] u; if (dfs(v)) { return true; } } } color[u] 2; return false; } }4.2 prev数组与环路径提取的细节这段代码里最核心也最容易写错的部分是环路径的提取。为什么需要一个prev数组因为DFS在搜索时会形成一棵DFS树每个灰色节点都有一个从哪来的前驱节点。当发现一条边u - v而v是灰色时说明在DFS树上从v到u有一条路径再加上u - v这条边就围成一个环。提取过程用一个简单例子推演假设图是1-22-33-1DFS从1进入路径是1-2-3此时在节点3发现邻居1是灰色。回溯提取时cur从3开始把3加入路径然后cur prev[3] 22不等于目标节点1把2加入路径继续cur prev[2] 1此时cur等于目标节点1退出循环再把1加入路径。现在的路径是[3,2,1]用Collections.reverse反转成[1,2,3]最后再追加一次目标节点1变成[1,2,3,1]这样就输出了一个完整闭合的环。这里有个细节值得注意途中加入的节点顺序是从u一路回溯到v和环的实际走向是反的所以必须反转。很多同学第一次写的时候忘了反转导致输出顺序不对被判错。关于环的起点我的实现中以DFS发现环时的v作为起点即环中第一个被当前路径遇到的节点。如果题目要求从环上编号最小的节点开始输出只需要在得到cyclePath后找到最小值对应的位置把前面的部分拼到后面即可这属于输出格式的适配问题。4.3 输入性能Scanner和BufferedReader的选择Java的Scanner在数据量小的时候完全够用但OD机试部分题目会把N压到10^6级别这时候直接用Scanner逐行读整数很容易超时。更稳妥的做法是换成BufferedReader配合StringTokenizer或者split。BufferedReader br new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st new StringTokenizer(br.readLine()); int n Integer.parseInt(st.nextToken()); int m Integer.parseInt(st.nextToken());用BufferedReader读整数的速度大约是Scanner的几倍到十几倍差距非常明显。但Scanner的优点是代码短、不容易写错适合时间紧张时快速提交。我的建议是平时练习时两种都写一遍考场上如果题目明确N范围不大用Scanner节约心智消耗如果N范围不明或很大直接上BufferedReader。5. Go实现从Java迁移的关键差异5.1 完整代码Go版本的逻辑和Java版本完全一致但Go的标准库没有Scanner.nextInt()这种便捷方法需要自己用bufio.Scanner读行、再通过strconv.Atoi转整数。这里给出完整可提交的代码package main import ( bufio fmt os strconv strings ) var ( graph [][]int color []int prev []int cyclePath []int ) func main() { scanner : bufio.NewScanner(os.Stdin) scanner.Scan() parts : strings.Fields(scanner.Text()) n, _ : strconv.Atoi(parts[0]) m, _ : strconv.Atoi(parts[1]) graph make([][]int, n1) color make([]int, n1) prev make([]int, n1) for i : range prev { prev[i] -1 } for i : 0; i n; i { graph[i] make([]int, 0, 4) } for i : 0; i m; i { scanner.Scan() parts strings.Fields(scanner.Text()) from, _ : strconv.Atoi(parts[0]) to, _ : strconv.Atoi(parts[1]) graph[from] append(graph[from], to) } for i : 1; i n; i { if color[i] 0 dfs(i) { var sb strings.Builder sb.WriteString(有环警告: ) for j, node : range cyclePath { if j 0 { sb.WriteString(-) } sb.WriteString(strconv.Itoa(node)) } fmt.Println(sb.String()) return } } fmt.Println(无环主次关联关系合法) } func dfs(u int) bool { color[u] 1 for _, v : range graph[u] { if color[v] 1 { cyclePath cyclePath[:0] cur : u for cur ! v { cyclePath append(cyclePath, cur) cur prev[cur] } cyclePath append(cyclePath, v) for i, j : 0, len(cyclePath)-1; i j; i, j i1, j-1 { cyclePath[i], cyclePath[j] cyclePath[j], cyclePath[i] } cyclePath append(cyclePath, v) return true } if color[v] 0 { prev[v] u if dfs(v) { return true } } } color[u] 2 return false }5.2 Java与Go实现细节对照两种语言解决同一个问题思路一致但落到代码上差异点不少。这里做一份对照方便熟悉其中一种语言的同学快速迁移。对比项JavaGo图存储ArrayListArrayListInteger[][]int切片颜色数组int[] color[]int反转列表Collections.reverse()手写双指针交换字符串拼接System.out.printstrings.Builder读取输入Scanner.nextInt()bufio.Scannerstrconv.Atoi异常处理不强制Atoi返回错误OJ场景直接忽略Go中make([][]int, n1)创建的切片每个元素默认是nil往里面append前必须初始化。我的代码里用graph[i] make([]int, 0, 4)做了预分配容量4可以容纳大多数节点的出边数能减少切片扩容次数。如果节点编号上限很大但边很稀疏预分配容量反而会浪费一点内存但这种级别的开销对OJ来说完全不是问题。5.3 bufio.Scanner和递归深度的坑bufio.Scanner有个容易被坑的点默认最大读取单行长度是64KB如果某一行数据特别长扫描器会报错直接中断。这道题输入每一行只有两个整数完全不用担心但有些OD题目会把大量数据放在同一行里那就需要显式调大Scanner的缓冲区scanner : bufio.NewScanner(os.Stdin) scanner.Buffer(make([]byte, 1024*1024), 1024*1024)另外Go的递归栈虽然是动态增长的但并不意味着可以无限递归。对于10^6规模的链式图递归层级可能直接压爆栈。如果N很大建议用显式栈替代递归实现DFS或者换成Kahn拓扑排序。OD机试C卷的数据量通常在可控范围内但作为备考还是要知道这个风险点。关于Go 1.22之前的循环变量陷阱for _, v : range graph[u]里的v在每次迭代中是复用的如果你在循环体内把v的地址保存下来后续取值可能全部指向最后一个元素。我们这里直接用值判断不涉及取地址所以没有风险但遇到需要把循环变量传给协程的场景就要格外小心。6. 双机位C卷实战考场上最容易翻车的点6.1 提交环境与代码规范细节OD机试的C卷是双机位监考模式需要在一个摄像头对着人脸、另一个摄像头对着屏幕和键盘的环境下完成。这意味着你的整个编码过程会被录制审查尤其是切屏、打开其它应用这类行为很容易被判违规。这种模式下最好的策略就是考前把代码模板、常用算法默写熟练考场上全程在一个编辑器里完成不切屏、不查资料。代码规范方面Java提交时类名必须是Main不能带package声明否则直接编译失败。Go提交时必须是package main并且要有func main()入口。这些看似基础的细节每年都能刷掉一批人。6.2 高频低级错误清单把我在刷题群和实际辅导里见过的翻车情况汇总一下主要集中在下面几类建图方向反了。题目说次单指向主单代码里却写成主单指向次单。对于判环本身反向后如果原图有环反转后依然有环判断结果不会错但如果题目还有其它隐藏条件方向反了就可能影响最终结果。数组越界。节点编号有时候从1开始有时候从0开始没有仔细看清就开数组下标直接越界。我的代码统一采用n1大小、从1开始是这类题目最保险的写法。递归里忘记把当前节点标记为黑色。漏掉color[u] 2这一行后已经访问完的节点永远保持灰色导致后续路径全部误判成环。环路径输出少了最后一个回到起点的节点。题目要的是1-2-3-1这种闭合形式很多人在反转后直接输出[1,2,3]丢掉了闭环。我在代码里用cyclePath.add(v)补了一次起点这里很容易被忽略。Scanner不关闭。OJ环境里不关闭资源一般不会判错但如果你在循环里反复创建Scanner可能触发内存问题。多组测试用例没处理。部分题目会一次性给多组数据或者第一行给一个T表示组数。我给的代码按单组数据写如果你在考场上发现样例连续输出了两次结果就要考虑外层循环读T。6.3 这类题目的备考延伸方向主次关联成环警告的本质是有向图判环它还有一个更贴近日常开发的变体检测线程依赖是否形成死锁。多个线程各自持有锁并等待其它线程释放锁把线程编号和等待关系建成有向图后检查环是否存在是死锁检测的核心手段。这个概念在Java并发编程和操作系统面试里都会遇到OD机试把它包装成采购单主次关联场景考查的图论知识是完全相通的。备考时建议把这一类题归并到一起刷拓扑排序、并查集、有向图判环、无向图判环这四个题型的模板代码各自默写一遍。C卷的题目整体难度会比A/B卷略高但核心考点基本不会超出这些经典算法的范围。真正拉开分差的往往不是算法本身而是你对输入输出模式的熟悉程度和边界条件的敏感度这两样只能靠多写完整代码练出来。我个人在实际备考中有一个习惯每道真题不管多简单都会分别用两种语言完整提交一遍。Java版本用来检查自己的面向对象思维和异常感知Go版本用来检查对内存布局和切片操作的敏感度。这两种语言在判环这道题上的差异其实不大但通过这种强制练习能逼自己把每个细节都搞清楚而不是背个模板就上场。等你闭着眼能把prev数组的回溯过程在白板上画出来这道题就彻底吃透了。
阅读完成 · 觉得有帮助？
