题目描述

给定一个n个点m条边的无向图，图中可能存在重边和自环。

请你判断这个图是否是二分图。

样例

4 4
1 3
1 4
2 3
2 4

Yes

算法1

(染色法DFS)

1. 因为要 建图，所以还是用到了e[M], ne[M]这些一系列。使用邻接表来建图，因为是无向图，所以边数M是点数N的2倍。
2. 新建一个flag变量，标志 是否为二分图。二分图的概念是图中不包含 奇数环。逻辑是把整个图中的所有节点分成2个点集，让所有的边出现在2个点集之间。
3. dfs(i)则是判断，如果节点i未被染色，就通过dfs(i)把i所在的连通块整个都染一遍。
4. dfs(o, c)函数内部，它是bool型，先将传入的节点o的颜色染为c。接下里处理节点o的所在连通块。
5. 首先o和j是一条边上2个不同的端点，如果j还没有被染色，就以3 - c(相反的颜色)去染节点j。这里调用了dfs()函数，如果返回false说明失败，直接返回false。
6. 如果节点j已经被染了颜色，则看看节点j的颜色和节点o的颜色是否不同，如果相同则也说明失败，return false。
7. dfs()中for()循环结束后，如果还没有return false，说明染色过程没有产生矛盾，则说明 是二分图，dfs()函数的最后则return true。
8. main()函数中的for()循环则是遍历每个节点，如果发现节点i没有被染色，那么放进dfs()中去让它染色。染色过程中如果出现了矛盾，就说明该图 不是一个二分图，置flag为false，然后直接break。
9. 最后这里break后说明不用再遍历下去了有点没理解，是因为一个节点的连通块染色失败了，那么整个图直接都被判为失败吗？

时间复杂度

$O(n)$

C++ 代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 100010, M = 200010;  // **3   TLE

int h[N], e[M], ne[M], idx;
int n, m;
bool st[N];
int color[N];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

bool dfs(int o, int c)
{
    color[o] = c;  // **1 标记初始化
    for(int i = h[o]; ~i; i = ne[i])
    {
        int j = e[i];
        if(!color[j])
        {
            if(!dfs(j, 3 - c)) return false;
        }
        else
        {
            if(color[j] == c) return false;
        }
    }

    return true;
}

int main()
{
    memset(h, -1, sizeof h);

    scanf("%d%d", &n, &m);

    while(m --)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        add(u, v), add(v, u);
    }

    bool flag = true;               // **2

    /*
    for(int i = 1; i <= n; i ++)
        if(!dfs(i, 1))
            flag = true;
    */

    for(int i = 1; i <= n; i ++)
        if(!color[i])
        {
            if(!dfs(i, 1))
            {
                flag = false;
                break;
            }
        }

    if(flag == true) puts("Yes");
    else puts("No");

    return 0;
}

算法2

(染色法BFS)

1. 整体逻辑跟dfs是一样的，写面说说细微的几点不同。
2. 使用vector来存储邻接表，而不是数组模拟，好处是方便，坏处是效率。具体可以看代码。
3. bfs()的for循环中，碰到没有染色的节点，直接给染色，然后加入队列queue，队列中维护的就是染过色的节点。
4. 我这里犯了一个错误，就是开始的节点o的颜色是1，后面节点x的颜色直接就给3 - 1了，其实不对，这时候连接节点x的另一个端点it的颜色不一定是1，所以写成3 - color[it]才正确。
5. 对用vector建立邻接表的理解还不是很深，再多请教请教大佬。

C++代码

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

const int N = 100010, M = 200010;

int n, m;
int color[N];
vector<int> e[M];

bool bfs(int o)
{
    color[o] = 1;
    queue<int> q;
    q.push(o);

    while(q.size())
    {
        auto it = q.front();
        q.pop();

        for(auto x : e[it])
        {
            if(!color[x])
            {
                // color[x] = 3 - 1;                 // **1
                color[x] = 3 - color[it];
                q.push(x);
            }
            else
            {
                if(color[x] == color[it]) return false;
            }
        }
    }

    return true;
}

int main()
{
    scanf("%d%d", &n, &m);
    while(m --)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        e[a].push_back(b);
        e[b].push_back(a);
    }

    bool flag = true;
    for(int i = 1; i <= n; i ++)
    {
        if(!color[i])
        {
            if(!bfs(i))
            {
                flag = false;
                break;
            }
        }
    }

    if(flag) puts("Yes");
    else puts("No");

    return 0;
}