企业官网建设流程全解析

前几天整理春招笔试复盘，翻到蚂蚁集团2026届算法岗3月15日这一场的第二题，名字叫节点分类器。第一眼看到这个名字，我以为是机器学习里的分类任务，点进去才发现是个图论题：给你一张无向图，给每个节点打上0或1的标签，要求任意一条边的两个端点标签不能相同，最后输出字典序最小的合法方案，如果无解就输出-1。刚好我笔试时同时练了Java、C++和Python三个版本，趁着记忆完整，把题目、建模过程、代码实现和自测方法一起写出来。不管你是准备算法岗笔试还是想复习二分图，这篇都能直接拿去用。

1. 题目回顾：蚂蚁春招的“节点分类器”到底在问什么

1.1 输入输出格式

我把题目还原成下面这个版本，边界条件和原题保持一致：

给定 n 个节点（编号 1~n）和 m 条无向边。需要为每个节点分配标签 label_i ∈ {0,1}，使得对任意边 (u,v)，都有 label_u != label_v。若存在方案，输出字典序最小的合法标签序列；若不存在，输出 -1。

输入格式：第一行两个整数 n, m；接下来 m 行每行两个整数 u, v 表示一条无向边。

输出格式：若可行，输出一行 n 个整数，空格分隔；否则输出 -1。

数据范围：1 ≤ n ≤ 10^5，0 ≤ m ≤ 2×10^5。无自环，重边不影响答案。

注意 m 可以为 0，也就是说图可能完全没有边，所有节点都是孤立点。这种情况也要能正确处理，后面我会专门提到。

1.2 三个样例，先建立直觉

样例一：

输入：

3 2 1 2 2 3

输出：

0 1 0

这是一个链状的图：1 连 2，2 连 3。标签 0、1、0 满足任意相邻节点不同。如果输出 1、0、1 也是合法的，但题目要求字典序最小，所以节点 1 必须取 0。

样例二：

4 1 2 3

输出：

0 0 1 0

节点 1 是孤立点，可以取 0。节点 2 和节点 3 之间有边，节点 2 在这个连通块中第一次出现，为了让字典序最小，节点 2 取 0，节点 3 只能取 1。节点 4 同样是孤立点，取 0。

样例三：

3 3 1 2 2 3 3 1

输出：

-1

三个节点两两相连，形成一个三角形。想用 0/1 两个标签让每条边两端都不同是不可能的，因为这是一个奇环，二分图判定直接失败。

1.3 数据范围决定了用什么算法

n 到 10^5，m 到 2×10^5，这两个数字一出来，基本就锁定了 O(n+m) 的图遍历方案。你不能用邻接矩阵，因为 n 是 10^5 时矩阵直接爆内存；也不能对每个节点单独做全图搜索，更不可能去枚举 2^n 种标签方案。正确做法是邻接表存图，然后一次遍历完成染色。

另外，图不保证连通，意味着只从节点 1 开始搜索是不够的。你必须保证每个连通分量都被处理过，这个问题在笔试里非常常见，也最容易漏。还有一个容易被忽视的点：n=10^5 的链状图会让 DFS 递归深度达到 10^5，Java/C++ 的默认递归栈都可能爆掉，Python 即使设置递归上限也不一定稳。所以下面我全部用 BFS 实现，队列不会出现栈深度问题。

2. 建模思路：从“标签不同”到二分图染色

2.1 核心等价关系

题目说每条边两端必须不同，这不就是给图染两种颜色吗？0 和 1 就是两种颜色，相邻节点不能同色。一个图如果能用两种颜色完成染色，使得所有边两端异色，这个图就是二分图。所以“节点分类器”这个看起来很业务化的名字，本质上是“二分图判定 + 输出染色方案”。

二分图的经典判定方法就是染色法：从一个节点开始染成 0，它的所有邻居染成 1，邻居的邻居再染成 0，逐层扩散。如果在扩散过程中发现一个节点已经被染过色，但和当前节点颜色相同，那就说明出现了矛盾，图不是二分图。

2.2 BFS 染色的完整流程

我用的 BFS 染色步骤如下：

1. 初始化 color 数组，长度为 n+1，全部赋值为 -1，表示未染色。
2. 从 1 到 n 枚举每个节点 i。如果 color[i] != -1，说明它已经属于之前某个连通分量，跳过。
3. 如果 color[i] == -1，说明 i 是一个新连通分量里第一次被访问的节点。为了满足字典序最小，直接令 color[i] = 0，将 i 加入队列。
4. 从队列中取出节点 u，遍历它的所有邻居 v：
   • 如果 color[v] == -1，说明 v 还没有被访问过，把 color[v] 设为 1 - color[u]，然后入队。
   • 否则，检查 color[v] 是否等于 color[u]。如果相等，说明一条边两端被分到了同一类，直接标记失败并结束。
5. 所有连通分量处理完之后，如果失败，输出 -1；否则输出 color[1] 到 color[n]。

这里的关键点是：外层 for 循环一定要走完所有节点。无论图有多少个连通分量，都能被覆盖到。

2.3 字典序最小是怎么保证的

题目要求输出字典序最小的标签序列，很多人会在这里卡住。其实每个连通分量只有两种染色方案：要么把起点染成 0，要么把起点染成 1，之后所有节点的颜色都会因为连通性被唯一确定。不同连通分量之间互不影响。

所以要得到字典序最小，只需要按节点编号从小到大扫描，每次遇到一个未染色的节点，就把它作为当前连通分量的起点，并且固定染成 0。为什么这是对的？因为当前节点之前的所有位已经固定了，当前位如果取 0 一定比取 1 小，后面无论怎么安排都无法弥补这一位的差距。这个贪心策略在不同连通分量之间不会互相干扰，所以全局一定是字典序最小。

如果原题并没有要求字典序最小，这个策略也完全合法，因为它只是从每个连通分量的两个可行方案中选了字典序更小的那个，属于合法方案中的一种。所以按照更严格的版本实现，反而更稳。

2.4 正确性证明和复杂度

正确性可以从两个方向看：

如果 BFS 染色过程中没有冲突，那么最终每个节点的颜色都满足所有邻居颜色不同，这就是一个合法的标签方案。

如果 BFS 过程中出现了邻居颜色相同，说明从起点到这个节点的两条路径长度奇偶性相同，再加上这条边会构成一个奇环。二分图不能包含奇环，所以无解。反过来，如果一个图是二分图，那么任意起点染色后，每个节点的颜色由它到起点的距离奇偶性唯一决定，BFS 一定不会冲突。

复杂度方面，每个节点最多入队出队一次，每条无向边在邻接表里被访问两次，总复杂度是 O(n+m)，空间复杂度同样是 O(n+m)。这个数量级在 10^5 的数据范围内非常安全。

3. 三种语言实现与关键细节

3.1 Java 版本：用 ArrayDeque 和 BufferedReader

import java.io.*; import java.util.*; public class NodeClassifier { public static void main(String[] args) throws IOException { 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()); List<Integer>[] g = new List[n + 1]; for (int i = 1; i <= n; i++) { g[i] = new ArrayList<>(); } for (int i = 0; i < m; i++) { st = new StringTokenizer(br.readLine()); int u = Integer.parseInt(st.nextToken()); int v = Integer.parseInt(st.nextToken()); g[u].add(v); g[v].add(u); } int[] color = new int[n + 1]; Arrays.fill(color, -1); Queue<Integer> queue = new ArrayDeque<>(); boolean ok = true; for (int i = 1; i <= n && ok; i++) { if (color[i] != -1) continue; color[i] = 0; queue.offer(i); while (!queue.isEmpty()) { int u = queue.poll(); for (int v : g[u]) { if (color[v] == -1) { color[v] = 1 - color[u]; queue.offer(v); } else if (color[v] == color[u]) { ok = false; break; } } if (!ok) break; } } if (!ok) { System.out.println(-1); } else { StringBuilder sb = new StringBuilder(); for (int i = 1; i <= n; i++) { if (i > 1) sb.append(' '); sb.append(color[i]); } System.out.println(sb); } } }

Java 版本有几个细节要注意：

• 队列用ArrayDeque而不是LinkedList，笔试数据量大时ArrayDeque更快，也不支持 null，不会有问题。
• 读入用BufferedReader而不是Scanner。m 到 2×10^5 时 Scanner 虽然也能过，但没必要冒险。
• 发现矛盾后可以立刻 break，不需要把整个图遍历完，最后输出 -1 就行。
• 输出用StringBuilder拼接，避免循环里多次调用System.out.print。

3.2 C++ 版本：关同步 + vector 邻接表

#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; vector<vector<int>> g(n + 1); for (int i = 0; i < m; i++) { int u, v; cin >> u >> v; g[u].push_back(v); g[v].push_back(u); } vector<int> color(n + 1, -1); queue<int> q; bool ok = true; for (int i = 1; i <= n && ok; i++) { if (color[i] != -1) continue; color[i] = 0; q.push(i); while (!q.empty() && ok) { int u = q.front(); q.pop(); for (int v : g[u]) { if (color[v] == -1) { color[v] = 1 - color[u]; q.push(v); } else if (color[v] == color[u]) { ok = false; break; } } } } if (!ok) { cout << -1 << '\n'; } else { for (int i = 1; i <= n; i++) { if (i > 1) cout << ' '; cout << color[i]; } cout << '\n'; } return 0; }

C++ 版本里我关了cin和stdio的同步，并绑定了cin.tie(nullptr)，这样cin的读入速度足够应对 2×10^5 条边。如果你实在担心，也可以直接用scanf，但关了同步之后cin在这道题完全够用。

vector<vector<int>>是最简单直观的邻接表写法。对于这种笔试场景，不需要手工链表，也不用unordered_map，vector 的缓存友好度足够好。

3.3 Python 版本：一次读入 + deque

import sys from collections import deque def solve(): data = list(map(int, sys.stdin.buffer.read().split())) if not data: return it = iter(data) n = next(it) m = next(it) g = [[] for _ in range(n + 1)] for _ in range(m): u = next(it) v = next(it) g[u].append(v) g[v].append(u) color = [-1] * (n + 1) ok = True for i in range(1, n + 1): if not ok: break if color[i] != -1: continue color[i] = 0 q = deque([i]) while q and ok: u = q.popleft() for v in g[u]: if color[v] == -1: color[v] = 1 - color[u] q.append(v) elif color[v] == color[u]: ok = False break if not ok: sys.stdout.write("-1\n") else: sys.stdout.write(" ".join(map(str, color[1:])) + "\n") if __name__ == "__main__": solve()

Python 版本最值得注意的就是读入方式。sys.stdin.buffer.read().split()一次性读入所有数据，再一次性转成 int，比循环调用input()快非常多。m 到 2×10^5 的时候，读入方式可能就是能不能过题的关键。

队列用deque，不要用list配合pop(0)，后者是 O(n) 操作，在 10^5 级别的节点下会退化。

3.4 为什么我不推荐 DFS 和并查集

DFS 染色当然是正确的，但存在一个现实问题：递归深度。最坏情况下图是一条链，DFS 会一路递归到第 10^5 层。Java 和 C++ 的默认栈不一定扛得住，Python 即使设置了sys.setrecursionlimit(10**6)，在一些环境下仍然可能出现段错误或者进程崩溃。虽然可以手写栈模拟递归，但代码复杂度就上去了，不如 BFS 队列直接。

并查集扩展域（也叫种类并查集）也能判断二分图，做法是维护每个节点“和根节点同色”或“和根节点异色”的约束关系。但题目要求输出每个节点的具体颜色，用种类并查集判断完成后，还需要额外遍历一遍图来分配颜色，代码量并不小。相比之下，一次 BFS 同时完成判定和输出，是最贴合笔试场景的方案。

4. 在线测试：样例、边界用例与自测脚本

4.1 三个样例跑通

三个版本的代码我都本地跑过，结果如下：

这三个用例基本覆盖了合法、多连通块、非法三种核心情况，能跑对之后大部分逻辑已经没问题。

4.2 边界用例清单

我自测时还会额外跑下面这些边界，每一条都值得过一遍：

重边的情况下，第二次遍历到同一条边时，两个端点已经染色，但是颜色一定不同，所以不会误判。自环就比较特殊：一个节点的邻居包含自己，检查color[v] == color[u]时肯定是相等的，所以会直接返回 -1。虽然原题保证了无自环，但防御性写代码总没坏处。

4.3 在线自测的“正确姿势”

如果你不是在某个 OJ 上直接提交，而是想验证自己本地改过的版本，我建议写一个 checker。把原图存进in.txt，把算法输出保存到out.txt，然后用下面的 Python 脚本校验：

import sys def main(): in_file, out_file = sys.argv[1], sys.argv[2] with open(in_file) as f: data = f.read().split() it = iter(data) n = int(next(it)) m = int(next(it)) edges = [] for _ in range(m): u = int(next(it)) v = int(next(it)) edges.append((u, v)) with open(out_file) as f: line = f.read().strip() if line == "-1": print("AC (no solution)") return labels = list(map(int, line.split())) if len(labels) != n: print(f"WA: label count mismatch, expected {n}, got {len(labels)}") return if any(x not in (0, 1) for x in labels): print("WA: label must be 0 or 1") return for u, v in edges: if labels[u - 1] == labels[v - 1]: print(f"WA: edge {u}-{v} has same label {labels[u - 1]}") return print("AC") if __name__ == "__main__": main()

这个 checker 做的事情很简单：如果输出是 -1，就认为答案合法；否则检查长度、0/1 合法性和每条边两端是否不同。这其实就是 OJ 里 special judge 的简化版。用这种方式自测，比自己肉眼确认结果可靠得多。

4.4 大数据量下的表现

在 n=10^5、m=2×10^5 的规模下，三种语言跑完整的 BFS 遍历，时间理论上都在百毫秒级别。Python 会稍慢一点，但只要读入方式正确、输出方式正确，1 秒内完成问题不大。真正可能拖慢速度的往往是输出：Java 用 StringBuilder，Python 用" ".join，C++ 用循环加cout << ' '控制，不要每输出一个数就 flush 一次。

5. 考场复盘：我在这个题上踩过的坑和提速技巧

5.1 最大的坑：只从一个节点开始 BFS

我第一次写这题的时候，只对节点 1 做了一次 BFS，然后直接输出 color 数组。样例过了，但是遇到多连通块的数据就挂了：节点 2、节点 3 那边全是 -1，输出出来变成一堆 -1，而且完全没检查到非法边。说白了就是没有意识到图不连通。这个坑太经典了，十次里有八次会在多连通分量上翻车。

正确做法就是外层for i in 1..n，把每个未染色节点都当作新的连通分量起点。这一个循环加进去，问题就解决了。

5.2 读入与输出细节不能忽略

笔试的时候，输出格式往往比算法更坑。这题要求输出一行 n 个整数，末尾可以有换行，但最好不要有多余空格。我见过有人用循环输出color[i] + " "，最后多了一个空格，虽然有的 OJ 会忽略，但有的不会。所以代码里我统一处理成“非第一个数前面加空格”。

读入方面，m 可能是 0，意味着接下来没有边行。如果你用input()或readLine()循环 m 次，没问题；但如果你在读完第一行之后，想当然地再调用一次nextLine()来跳过空行，就可能在 m=0 时错误读取。所以最稳的方式是直接用分词读入，不依赖行结构，也就是 Java 的StringTokenizer、C++ 的cin >>、Python 的read().split()。

5.3 面试官可能追问的变形

这题写完不代表结束。算法岗面试官很喜欢在笔试题目基础上追问，常见的有这么几个变形：

• 如果部分节点已经有固定标签，怎么判断整张图是否合法？答案是：把已有标签当作初始颜色，从未染色节点开始 BFS，遇到冲突就返回 -1。
• 如果要求统计合法方案数呢？每个连通分量有两种染色方案，设连通分量个数为 c，合法方案数是 2^c。但如果题目要求字典序最小，方案就唯一了。
• 如果标签有三类，要求每条边两端不同，还是二分图染色方法吗？不是。三色图染色是 NP-hard 问题，复杂度会完全不一样。面试官问到这里其实是在试探你对问题边界的理解。

这些变形不需要全部准备到代码级别，但脑子里要能立刻说出思路，不然面试官会觉得你只是背了一个模板。

5.4 稳定的做题节奏

我自己的做题习惯是：拿到题先看数据范围，n=10^5 基本确定要 O(n+m)；然后花三十秒时间做语义转换，把“相邻节点不能同类”翻译成“二分图染色”；最后十分钟内完成 BFS 实现和样例验证。节点分类器这题从理解题意到提交，应该压缩在十五分钟以内。

如果考试时一时想不起来“字典序最小”怎么保证，先不要慌。记住一条原则：每个新连通块第一次遇到的节点染 0。这句话足够解决所有因为多连通块或字典序引起的疑惑。

最后说点我自己的体会。节点分类器这个名字听起来很唬人，但剥开外包装就是一个二分图染色模板题。真正决定你能不能拿分的不是会不会 BFS，而是能不能快速识别出“相邻互斥”这类关系。准备算法岗笔试的时候，我建议把这种“转化型模板题”多刷几道，练到一看到“每条边两端必须不同”“分成两类互相独立”“染色不冲突”就能条件反射想到二分图。后面就算蚂蚁改一个场景，把用户换成商品、把边换成同时出现，底层解法还是一样的。