题目内容

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

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

输入格式

第一行包含两个整数n和m。

接下来m行，每行包含两个整数u和v，表示点u和点v之间存在一条边。

输出格式

如果给定图是二分图，则输出“Yes”，否则输出“No”。

数据范围

1≤n,m≤10^5

输入样例

4 4
1 3
1 4
2 3
2 4

输出样例

Yes

题解

二分图又称作二部图，是图论中的一种特殊模型。 设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为一个二分图。
二分图存在两个性质
性质一：一个图如果是二分图，那么这个图一定可以被二染色。
性质二：二分图当且仅当图中不含有奇数环（环的点数为奇数为奇数环）。

代码思路如下：
for(int i = 1; i <= n; i++){
if i未被染色：
dfs(i，颜色编号); //用深度优先遍历，把i所在的连通块整个染一遍颜色
}

代码

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 100010, M = 200010;

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

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

bool dfs(int u,int c){
    color[u] = c;
    
    for(int i  = h[u]; i != -1; 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(){
    scanf("%d%d", &n,&m);
    
    memset(h, -1, sizeof h);
    
    while(m--){
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b),add(b,a);
    }
    
    bool flag = true;
    for(int i  = 1;i <= n; i++){
        if(!color[i]){
            if(!dfs(i,1)){
                flag = false;
                break;
            }
        }
    }
    
    if(flag) puts("Yes");
    else puts("No");
    
    return 0;
    
}