二分图的概念及其判断

emptysetvvvv · 2019-06-01 09:22:17 · 个人记录

1\ [二分图概念]

• 【概念】二分图：若图中的点可以划分为左右两个集合，使得所有边均由一个集合连向另一个集合，即图中没有边数为奇数的环（\mathrm{e.g}三角形），这样的图称为二分图。

• 【链接】二分图的基本概念

2\ [二分图判断]

• 【方法】染色法：从任意一点开始，与他相邻的点染成异种颜色，若遇到相邻同色点则不为二分图。dfs 复杂度O(m).

• 【代码】

  bool dfs(int x, bool color) {
        col[x] = color;
        for(int i = head[x]; i; i = edge[i].next)
            if(col[e[i].to] == col[x]) return false;
            else if(!col[e[i].to] and !dfs(edge[i].to, !color)) return false;
        return true;
  }

• 【方法】扩展域并查集：显然可行，判断冲突即可，若在同一个集合则矛盾。

• 【方法】带权并查集：相当于用距离染色，奇黑偶白。

两种并查集算法复杂度均为O(m).