有向图树判断：入度、并查集与DFS的边界陷阱

1. 从一道题说起判断“它是不是一棵树”到底在考什么“Is It A Tree?”这个题目名字看着简单但它是我见过的最容易让人掉以轻心的图论入门题之一。很多人第一反应是“判断有没有环不就行了”然后写完交上去WAWrong Answer到怀疑人生。这道题的核心不是考你会不会写并查集而是考你有没有把“树”的定义吃透以及能不能把定义翻译成严密的判断逻辑。先把结论摆在这里一张有向图是树当且仅当它满足三个条件——只有一个根节点入度为0的点恰好一个、除根以外所有节点入度恰好为1、整张图连通且无环。这三个条件缺一不可而且它们之间不是完全独立的有些条件可以互相推导但为了代码的健壮性我建议全部显式检查。这道题适合谁看如果你正在学并查集、图的遍历、或者准备算法面试和编程竞赛这道题是一个非常好的“定义理解训练”。它不需要复杂的算法但需要你对边界情况有极强的敏感度。我见过太多人并查集模板背得滚瓜烂熟结果在这道题上因为空树、森林、自环、多父节点这些情况翻车。接下来我会从题目本质、核心判断逻辑、并查集与DFS两种实现路线、边界情况处理、常见错误排查这几个维度把这道题彻底拆开讲清楚。每一部分都会附带我实际踩过的坑和验证过的代码你可以直接拿去对照自己的实现。2. 题目本质拆解树的定义与判断条件推导2.1 树的有向图定义到底是什么在无向图里树的定义很直观n个节点、n-1条边、连通、无环。但在有向图里事情变得微妙起来。这道题通常给出的输入是一系列有向边(u, v)表示从u指向v然后问你这些边构成的图是不是一棵以某个节点为根的树。有向图意义下的树也叫有根树或有向树需要满足恰好一个根节点这个节点的入度为0其他所有节点入度都为1。从根出发能到达所有节点也就是忽略方向后图是连通的且从根沿有向边可以走到每一个节点。没有环有向图中如果存在环那么环上的节点入度至少为1且无法从根到达必然违反树的性质。这里有个关键点入度为0的节点恰好一个这个条件非常强。它直接排除了森林多个根、排除了所有节点入度都大于0的情况必有环。但它不能单独保证连通性比如两个不相连的组件各自有一个入度为0的节点那入度为0的节点就有两个还是会被排除。但如果一个组件有根、另一个组件是一个环呢环上所有节点入度都为1没有入度为0的节点此时入度为0的节点仍然只有一个但图不连通且有环。所以光看入度不够还需要并查集或遍历来保证连通无环。2.2 三个判断条件的优先级与依赖关系我在实际写题时总结出一个判断顺序可以让你少写很多冗余代码先统计入度遍历所有边记录每个节点的入度。如果发现某个节点入度大于1直接判定不是树。因为树中除根以外每个节点只有一个父节点。再找根节点统计入度为0的节点个数。如果恰好为1这个节点就是候选根如果为0说明有环或者空图空图特殊处理如果大于1说明是森林不是树。最后判连通无环用并查集合并所有边如果合并时发现两个节点已经在同一集合说明有环不是树。合并完成后检查所有出现过的节点是否都在同一个集合中如果不是说明不连通。这个顺序的好处是入度检查是O(E)且常数极小能快速排除大量非法情况并查集负责处理环和连通性逻辑清晰。你也可以用DFS从根遍历看能否访问所有节点且无后向边但并查集写起来更短更适合竞赛场景。注意空图没有任何边、没有任何节点在这道题里通常被认为是树。这一点非常反直觉但很多OJ的题目描述里会明确说“空树也是树”。如果你不确定去看题目原文的样例通常会有0 0这样的输入表示结束而单独的0 0有时就是空树测试用例。2.3 为什么不能只用并查集判断环很多人觉得并查集能判环就够了但并查集判环只能保证“无环”不能保证“只有一个根”和“连通”。举个例子节点1-2-3形成一条链节点4-5-6形成另一条链两条链之间没有边。并查集合并时不会发现环但显然这是森林不是树。再比如节点1指向22指向33指向1这是一个环并查集合并到第三条边时会发现3和1已经在同一集合判定有环。但如果只有环没有其他节点入度为0的节点个数为0也能排除。所以并查集必须配合入度统计一起使用两者是互补的。3. 并查集实现路线从模板到AC的完整细节3.1 并查集模板的微调与路径压缩标准的并查集模板大家都会写但在这道题里有两个细节需要调整。第一节点编号不一定是连续的可能很大或者很稀疏所以不能用固定大小的数组需要用哈希表字典来存储父节点。第二需要记录所有出现过的节点方便最后检查连通性。先看核心的并查集结构parent {} def find(x): if x not in parent: parent[x] x return x # 路径压缩 if parent[x] ! x: parent[x] find(parent[x]) return parent[x] def union(x, y): rx, ry find(x), find(y) if rx ry: return False # 已经在同一集合说明有环 parent[rx] ry return True这段代码里find函数在遇到未记录的节点时会自动初始化这样就不需要提前知道节点范围。路径压缩用递归实现简洁但要注意递归深度如果节点数上万Python的递归限制可能触发可以改成迭代版本def find(x): if x not in parent: parent[x] x return x root x while parent[root] ! root: root parent[root] # 路径压缩 while parent[x] ! root: parent[x], x root, parent[x] return root迭代版本更稳妥推荐在竞赛中使用。3.2 入度统计与根节点判定入度统计用一个字典in_degree即可。遍历每条边(u, v)时in_degree[v] in_degree.get(v, 0) 1。同时把u和v都加入节点集合nodes。遍历完所有边后统计入度为0的节点roots [node for node in nodes if in_degree.get(node, 0) 0] if len(roots) ! 1: return False # 不是树空图除外这里有个坑如果图是空图没有任何边nodes是空集roots也是空列表len(roots) ! 1会返回False。但空图应该是树所以需要单独处理if not nodes: return True # 空树另外如果某个节点入度大于1也要直接返回False。这个检查可以在遍历边的时候顺便做if in_degree.get(v, 0) 1: return False3.3 合并过程中的环检测与最终连通性验证合并所有边的时候如果union(u, v)返回False说明u和v已经在同一集合加上这条边就会形成环直接判定不是树。合并完成后需要验证所有节点是否在同一个集合。由于并查集可能有多棵树每个集合一个根我们只需要检查所有节点的find结果是否都相同root_set set(find(node) for node in nodes) if len(root_set) ! 1: return False # 不连通这里有个优化其实在入度检查通过后如果并查集合并没有发现环且所有节点都在同一集合那么一定是一棵树。因为入度条件已经保证了只有一个根连通性保证了从根可达所有节点无环保证了路径唯一。完整的并查集解法代码def is_tree(edges): parent {} in_degree {} nodes set() def find(x): if x not in parent: parent[x] x return x root x while parent[root] ! root: root parent[root] while parent[x] ! root: parent[x], x root, parent[x] return root def union(x, y): rx, ry find(x), find(y) if rx ry: return False parent[rx] ry return True for u, v in edges: nodes.add(u) nodes.add(v) in_degree[v] in_degree.get(v, 0) 1 if in_degree[v] 1: return False if not nodes: return True roots [n for n in nodes if in_degree.get(n, 0) 0] if len(roots) ! 1: return False for u, v in edges: if not union(u, v): return False root_set set(find(n) for n in nodes) return len(root_set) 1这段代码我实测过多个OJ的测试数据包括空树、自环、多父节点、森林、单节点等边界情况都能正确通过。4. DFS/BFS遍历路线另一种思路与对比4.1 从根出发的遍历逻辑除了并查集另一种自然的思路是从根节点出发做一次DFS或BFS看能否访问到所有节点同时检测是否有环。具体步骤统计入度找到唯一的根节点入度为0。从根开始DFS标记访问过的节点。如果DFS过程中遇到已经访问过的节点且不是父节点说明有环。DFS结束后检查访问节点数是否等于总节点数不等则说明不连通。这个思路的难点在于“遇到已访问节点”的判断。在有向图中如果从根出发遍历遇到已访问节点不一定意味着环因为可能存在两条路径到达同一节点菱形结构。但在树中每个节点入度为1不可能有两条路径到达同一节点。所以如果入度检查已经通过每个非根节点入度恰好为1那么DFS中遇到已访问节点就一定是环。DFS实现def is_tree_dfs(edges): from collections import defaultdict graph defaultdict(list) in_degree {} nodes set() for u, v in edges: graph[u].append(v) nodes.add(u) nodes.add(v) in_degree[v] in_degree.get(v, 0) 1 if in_degree[v] 1: return False if not nodes: return True roots [n for n in nodes if in_degree.get(n, 0) 0] if len(roots) ! 1: return False visited set() stack [roots[0]] while stack: node stack.pop() if node in visited: return False # 有环 visited.add(node) for neighbor in graph[node]: stack.append(neighbor) return len(visited) len(nodes)注意这里用栈模拟DFS每次弹出节点时检查是否已访问。如果已访问说明有环。但这里有个细节如果图中存在自环节点指向自己入度检查时该节点入度为1自己指向自己根节点可能是其他节点DFS时从根出发可能根本到不了这个自环节点最后连通性检查会失败。但如果自环节点就是根呢根节点入度为0自环会让它入度变成1所以根节点不可能是自环节点。因此自环情况会被入度检查或连通性检查排除。4.2 两种方法的性能与适用场景对比对比维度并查集DFS/BFS时间复杂度O(E α(N))近似线性O(VE)空间复杂度O(V)O(VE) 需要存图代码长度中等中等环检测合并时自然检测需要额外visited判断连通性检测最后检查集合数遍历后检查访问数适用场景边动态加入、在线判断图结构固定、需要遍历顺序边界处理空图需特判空图需特判从竞赛角度并查集更通用因为很多图论题都是动态加边。但这道题边是一次性给出的两种方法都可以。我个人偏好并查集因为不需要建图内存占用更小而且逻辑更集中。实操心得如果题目输入规模很大比如10万条边DFS递归版本可能爆栈建议用迭代版或并查集。并查集的路径压缩在Python里用迭代写性能很稳。5. 边界情况全解析那些让你WA到崩溃的坑5.1 空树、单节点树与自环空树输入没有任何边节点集合为空。很多人的代码会返回False因为找不到根节点。但题目通常认为空树是树。处理方式就是在最前面加if not nodes: return True。单节点树输入只有1 1这样的自环不对单节点树应该是没有边的但节点存在。如果输入是1 1表示节点1指向自己这是一个自环不是树。如果输入是空边但题目给了节点通常不会节点都是从边里出现的。所以单节点树在输入里表现为空边和空树一样处理。但如果题目允许孤立节点出现比如先给节点数再给边那需要单独判断。自环节点指向自己。入度检查时该节点入度为1如果它是唯一入度为0的节点不可能因为它入度为1。所以自环会导致没有入度为0的节点如果只有自环或者根节点是其他节点但自环节点无法从根到达。两种情况都会被排除。5.2 森林、多父节点与环的混合情况森林多个入度为0的节点。入度检查直接排除。多父节点某个节点入度大于1。入度检查直接排除。环树一个连通分量是树另一个是环。入度为0的节点只有树根一个但并查集合并时环会被检测到或者最后连通性检查发现环上的节点不在树的集合里。菱形结构节点1指向2和32和3都指向4。节点4入度为2入度检查排除。长链自环1-2-3-44-4。节点4入度为2来自3和4入度检查排除。我整理了一个边界情况速查表输入情况入度检查并查集环检测连通性检查最终判定空图无节点无无树特判单条边 1-2根1无环连通树自环 1-1无根--非树森林 1-2, 3-4根1,3无环不连通非树多父 1-3, 2-3根1,2无环不连通非树环 1-2, 2-3, 3-1无根有环-非树树环 1-2, 3-4, 4-3根1有环不连通非树5.3 输入格式的陷阱与处理技巧这道题在不同OJ上的输入格式可能不同。常见的有两种第一种每行两个整数u v表示一条边以0 0结束一组测试以-1 -1结束所有输入。这种格式下0 0本身可能表示空树也可能只是组间分隔符需要看题目具体说明。第二种先给节点数和边数然后给边。这种更简单但要注意节点编号可能从0或1开始。处理多组测试时记得每组之间重置并查集和入度字典。我见过有人忘记重置导致上一组的数据污染下一组结果莫名其妙WA。import sys def solve(): case_num 1 edges [] for line in sys.stdin: line line.strip() if not line: continue u, v map(int, line.split()) if u -1 and v -1: break if u 0 and v 0: # 处理当前组 result is_tree(edges) print(fCase {case_num} is {a tree if result else not a tree}.) case_num 1 edges [] else: edges.append((u, v))这段代码处理了多组输入注意0 0触发一组判断-1 -1结束。如果题目要求空树也输出那么当edges为空时is_tree返回True。6. 常见问题与排查技巧实录6.1 为什么我的并查集判环了还是WA最常见的原因有三个。第一忘记检查入度大于1的情况。并查集只能判环不能判多父节点。比如1-3, 2-3并查集合并时不会发现环但节点3有两个父节点不是树。第二忘记检查连通性。并查集合并完所有边后如果有多个集合说明不连通。第三空树没特判返回了False。排查方法拿几个典型用例手动跑一遍。比如1 2 2 3 3 1 0 0应该输出not a tree1 2 2 3 0 0应该输出a tree0 0应该输出a tree如果题目支持空树。6.2 入度统计时节点编号不连续怎么办用字典而不是数组。字典的get方法可以处理不存在的键非常方便。不要试图用max_node来开数组因为节点编号可能很大比如10^9开数组会爆内存。6.3 多组测试数据之间的状态重置这是最容易忽略的坑。每组测试之间parent、in_degree、nodes都要清空。建议把is_tree写成一个函数每次调用时内部创建新的字典这样天然隔离。不要用全局变量否则重置起来容易漏。6.4 递归DFS爆栈的解决方案Python默认递归深度是1000如果树是一条长链1000个节点就会爆栈。解决方案有两个一是用sys.setrecursionlimit(100000)提高限制但治标不治本二是改用迭代DFS用栈模拟。我推荐迭代版稳定可靠。6.5 常见错误速查表错误现象可能原因解决方法空树WA没特判空图加if not nodes: return True森林WA没检查根节点数量统计入度为0的节点数多父WA没检查入度大于1遍历边时检查in_degree[v] 1环WA并查集没判环union返回False时直接判非树不连通WA没检查集合数最后检查len(root_set) 1多组WA状态没重置每组新建字典或清空爆栈RE递归太深改迭代或提高递归限制超时TLE并查集没路径压缩加路径压缩独家避坑技巧在本地测试时构造一个包含所有边界情况的测试文件包括空树、单节点、自环、森林、多父、环、树环、长链。每次修改代码后跑一遍确保没有回归。这个习惯帮我省了大量提交次数。7. 从这道题延伸出的图论判断思维这道题表面考的是“是不是树”实际上训练的是把自然语言定义翻译成代码逻辑的能力。树有三个等价定义无环连通图、n-1条边的连通图、每个非根节点入度为1且根唯一。不同定义对应不同的判断策略选择哪个定义决定了你的代码复杂度和边界处理难度。我个人的经验是优先选择能用最少状态判断的定义。比如入度条件只需要一个字典并查集只需要一个父指针字典两者结合就能覆盖所有情况。如果用DFS还需要建图、visited集合、递归栈状态更多出错概率更大。另外这道题也提醒我边界情况不是“特殊情况”而是定义的一部分。空树是不是树这取决于定义。如果定义说“树是连通无环图”空图不连通不是树。但如果定义说“树是n个节点n-1条边的连通图”n0时0个节点-1条边不成立。所以空树是不是树完全看题目怎么定义。做题前一定要读清楚题目对树的定义不要凭直觉。最后分享一个我常用的调试方法对于图论题写一个暴力验证函数用邻接矩阵或边列表直接模拟定义然后和你的优化算法对拍。随机生成小规模图节点数5以内边数10以内跑1000组看结果是否一致。这个方法能发现90%以上的逻辑错误。import random def brute_force(edges): # 暴力判断检查入度、连通性、环 if not edges: return True nodes set() in_deg {} for u, v in edges: nodes.add(u) nodes.add(v) in_deg[v] in_deg.get(v, 0) 1 # 入度检查 for n in nodes: if in_deg.get(n, 0) 1: return False roots [n for n in nodes if in_deg.get(n, 0) 0] if len(roots) ! 1: return False # 从根DFS检查连通和环 adj {n: [] for n in nodes} for u, v in edges: adj[u].append(v) visited set() stack [roots[0]] while stack: node stack.pop() if node in visited: return False visited.add(node) for nb in adj[node]: stack.append(nb) return len(visited) len(nodes) # 随机对拍 for _ in range(1000): n random.randint(0, 5) m random.randint(0, 8) edges [(random.randint(1, 5), random.randint(1, 5)) for _ in range(m)] r1 is_tree(edges) r2 brute_force(edges) if r1 ! r2: print(Mismatch:, edges, r1, r2) break这个对拍框架我用了很多次每次都能快速定位逻辑漏洞。如果你在准备算法竞赛强烈建议养成对拍的习惯。这道题虽然叫“Is It A Tree?”但它真正问的是“你能不能把树的定义完整地、无遗漏地翻译成代码”。把这道题吃透以后遇到“判断是不是森林”“判断是不是DAG”“判断是不是二分图”这类题你都会有一个清晰的判断框架先明确定义再找最小判断条件集最后处理边界。这个思维模式比任何模板都值钱。