二分图的判定

二分图首先是无向图，并且可将图中顶点分为两个集合，集合内的点没有边相连

无向图是二分图，当且仅当图中不存在奇数环，根据此定理，二分图可用染色法判定

存储结构采用邻接链表，n为顶点数，m为边数

int value[m], next[m], head[n], d;

memset(head, -1, sizeof(head));

color[i]标示顶点i被染的颜色（0或1），初始化为全-1，表示未染色

int color[n];

算法采用深度优先遍历实现，尝试用0、1两种颜色标记顶点，一个顶点被标记后，其邻接顶点应被标记为相反颜色，如果标记发生冲突，说明存在奇环不是二分图

冲突有两种形式：一是邻接顶点未染色但递归染色失败（染色一个邻接顶点后，要递归对邻接的邻接染色，在某次递归中出现第二种冲突）；二是邻接顶点已与自身染成同色

bool paint(int x, int c) {
    color[x] = c;
    for (int i = head[x]; i != -1; i = nxt[i]) {
        int y = value[i];
        if (color[y] == -1 && !paint(y, 1 - c) || color[y] == c)
            return false;
    }
    return true;
}

遍历所有顶点，只要有一个顶点未染色但递归染色失败，就说明不是二分图

bool flag = true;
for (int i = 0; i < n; i++) {
    if (color[i] == -1 && !paint(i, 0)) {
        flag = false;
        break;
    }
}

---