ACM图论模板：二分图判定与并查集实现

"这是一份ACM竞赛中的个人模板，包含二分图的两种判定方法：染色法和并查集法。" 在ACM（国际大学生程序设计竞赛）中，模板是参赛者常用的一种工具，它包含了常用算法和问题解决策略的代码框架。这个模板主要关注图论中的一个重要概念——二分图。二分图是图的一种特殊形式，其中的顶点可以被分为两个不相交的集合，使得每条边都连接不同集合中的顶点。 **二分图判定** 二分图的判定在图论中有着广泛的应用，例如匹配问题、最短路径计算等。模板提供了两种判定二分图的方法： 1. **染色法判定** 这个方法通过为每个节点分配颜色（通常用0和1表示）来进行判定。从一个未被着色的节点开始，尝试将其染色，并递归地对与其相邻的节点进行染色，如果相邻节点已经染了相同的颜色，则返回false，表示这不是一个二分图。如果所有节点都能成功染色且没有冲突，那么就是二分图。代码中的`dfs`函数实现了这一过程。 ```cpp bool dfs(int u, int key) { col[u] = key; for (int i = 0; i < g[u].size(); ++i) { int v = g[u][i]; if (col[v] == key) return false; if (col[v] != -1) continue; if (!dfs(v, key ^ 1)) return false; } return true; } ``` 2. **并查集判定** 并查集是一种用于处理集合动态合并与查询的数据结构。在这个场景下，我们可以将每个节点视为一个集合，如果节点之间存在边，就将它们所在的集合合并。如果最后所有节点都在同一个集合中，那么图是一个二分图。代码中的`getf`和`merge`函数分别用于查找集合代表节点和合并集合。 ```cpp int getf(int x) { return x == f[x] ? x : f[x] = getf(f[x]); } void merge(int a, int b) { int fa = getf(a), fb = getf(b); if (fa != fb) f[fb] = fa; } ``` **应用** 在ACM竞赛中，二分图的概念常用于解决各种问题，如最大匹配、最小割、图的着色等。染色法和并查集法都是高效且实用的算法，可以帮助选手快速解决问题。 这个模板提供了基本的二分图判定实现，对于参加ACM竞赛或进行图论学习的程序员来说，是非常有价值的参考资料。通过不断实践和优化，这些基础模板可以进一步扩展，以适应更复杂的问题和算法挑战。