题目描述

给定一个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

C++ 代码

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

#define N 106

int head[N],n,m,cnt;
int color[N];

struct edge
{
    int to,nex;
}e[N << 1];

void add(int from,int to)
{
    e[++cnt] = (edge){to,head[from]};
    head[from] = cnt;
}

bool dfs(int x,int num)
{
    color[x] = num;
    for (int i = head[x]; i; i = e[i].nex)
    {
        int too = e[i].to;
        if (!color[too])
        {
            if (!dfs(too , 3 - num))
                return false;
        }
        else
        {
            if (color[too] == num)
                return false;
        }
    }
    return true;
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int a,b;
        cin >> a >> b;
        add(a,b),add(b,a);
    }
    for (int i = 1; i <= n; i++)
    {
        if (!color[i])
        {
            if (!dfs(i , 1))
            {
                puts("No");
                return 0;
            }
        }
    }
    puts("Yes");
    return 0;
}