二分图

定义

二分图，是一种可以将所有点分成两个点集，同点集不连，异点集相连的图，如图：

像这样的图就是二分图。

如何判断二分图

显而易见的，想要构造一个不是二分图的图，我们可以通过构造环来看，毕竟从理论上来讲因该是可以从环来推出规律。

先构造一个三个点的奇环：显而易见，不是二分图

再来是四个点的偶环：可能一想不是二分图，但是画出来以后发现是二分图

再来是五个点的奇环：不用画图就显而易见，不是二分图

所以，我们发现其实这个二分图只要没有奇环就可以了

代码实现

判断奇环，只需要使用奇偶染色法就可以了，代码如下：

bool Dfs(int u, int c) { // vis : 0 - 未访问 ; 1 - 奇 ; 2 - 偶
    vis[u] = c;
    for(int i = hd[u]; i; i = e[i].nt) {
        int v = e[i].to;
        if(vis[v] == c) return false;
        if(vis[v] == 0 && !Dfs(v, 3 - c)) return false;
    }
    return ture;
}

// 调用
memset(vis, 0, sizeof(vis));
Dfs(1, 1); // true : 是二分图 false : 反之