题目描述

给定一个 n 个点 m 条边的无向图，图中可能存在重边和自环。
请你判断这个图是否是二分图。

输入格式

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

输出格式

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

数据范围

1≤n,m≤105

输入样例：

4 4
1 3
1 4
2 3
2 4

输出样例：

Yes

思路图示：

算法1

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e5+10,M=2e5+10;
int n,m,u,v;
int color[N];
int h[N],e[M],ne[M],idx;
void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
bool dfs(int u,int c)   //dfs染色过程：
{
    color[u]=c; //先标记一下当前点的颜色
    for(int i=h[u];i!=-1;i=ne[i])   //遍历当前点的所有邻点，
    {
        int j=e[i]; //用j表示当前邻点
        if(!color[j])   //(1)若该邻点还未染色，
        {   //注意此处{}不能省！
            if(!dfs(j,3-c)) //则将其染为另一种颜色
                return false;
        }
        else if(color[j]==c)    //(2)若该邻点已经染色，但与该点颜色相同，则产生矛盾
            return false;
    }
    return true;    //全体过程染色正常
}
int main()
{
    //邻接表勿忘初始化：
    memset(h,-1,sizeof h);
    cin>>n>>m;
    while(m--)
    {
        cin>>u>>v;
        //邻接表存储无向图：
        add(u,v),add(v,u);
    }
    bool flag=true; //标记是否有矛盾产生
    //逐个遍历各个点：
    for(int i=1;i<=n;i++)
    {
        if(!color[i])   //若该点未染色，
            if(!dfs(i,1))   //则将其染为1号颜色，同时进入dfs染色过程判断是否有矛盾产生
            {
                flag=false; //产生矛盾
                break;  //立即退出
            }
    }
    if(flag)
        puts("Yes");
    else
        puts("No");
    return 0;
}

算法2