给定一个 n n n 个点 m m m 条边的无向图，图中可能存在重边和自环。
请你判断这个图是否是二分图。
第一行包含两个整数 n n n 和 m m m。
接下来 m m m 行，每行包含两个整数 u u u 和 v v v，表示点 u u u 和点 v v v 之间存在一条边。
如果给定图是二分图，则输出 Yes，否则输出 No。
1 ≤ n , m ≤ 1 0 5 1 \leq n,m \leq 10^5 1≤n,m≤105
4 4
1 3
1 4
2 3
2 4
Yes
首先我们需要了解什么是二分图。二分图，顾名思义，就是可以把图中的节点分成两个集合，使得同一集合内的节点没有边相连。因此，如果给定的图是二分图，也就是说，可以用两种颜色对节点进行染色，使得相邻节点的颜色不同。因此，我们可以使用深度优先搜索（DFS）来实现二分图的判断。
具体来说，我们可以从任意一个节点开始，将其染成红色，并遍历与其相邻的节点，将这些节点染成蓝色。接下来，对于每个蓝色的节点，再遍历与其相邻的节点，将这些节点染成红色。重复以上操作，直到所有的节点都被染色。如果染色过程中出现了相邻节点颜色相同的情况，则说明给定的图不是二分图。
具体实现时，我们可以使用一个颜色数组 c o l o r color color，用来记录每个节点的颜色。初始时，所有节点的颜色都是未染色的（可以用 − 1 -1 −1 表示）。在 DFS 过程中，对于当前遍历到的节点 u u u，如果它没有被染色，则将其染成与其相邻节点的颜色相反的颜色，并继续遍历与其相邻的未染色节点；如果它已经被染色，并且颜色与与其相邻节点的颜色相同，则说明给定的图不是二分图。最终，如果所有的节点都被染色了，并且没有相邻节点颜色相同的情况出现，则说明给定的图是二分图。
DFS 的时间复杂度为 O ( n + m ) O(n+m) O(n+m)，其中 n n n 表示节点数目， m m m 表示边数目。
#include<iostream>
#include<cstring>
using namespace std;
const int N = 2e5+10;
int h[N], e[N], ne[N], idx;
int n,m;
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;//将点u染色为c
for(int i = h[u];i!=-1;i = ne[i]){//继续染色它的子结点
int j = e[i];//子结点编号
if(!color[j]){//如果子结点j未被染色，就将它染为与父结点不同的颜色
if(!dfs(j,3 - c)){//染色过程出现冲突
return false;
}
}else if(color[j] == c){//子结点颜色相同
return false;
}
}
return true;
}
int main(){
cin>>n>>m;
int u,v;
memset(h,-1,sizeof h);
while(m--){
cin>>u>>v;
add(u,v),add(v,u);
}
for(int i = 1;i<=n;i++)//可能存在非连通图
if(!color[i])
if(!dfs(i,1)){
cout<<"No";
return 0;
}
cout<<"Yes";
return 0;
}
除了 DFS，我们还可以使用广度优先搜索（BFS）来实现二分图的判断。
具体来说，我们可以从任意一个节点开始，将其染成红色，并将其入队列。接下来，每次从队列中取出一个节点 u u u，遍历与其相邻的节点 v v v。如果 v v v 没有被染色，则将其染成与 u u u 相反的颜色，并将其入队列；如果 v v v 已经被染色，并且颜色与 u u u 相同，则说明给定的图不是二分图。
具体实现时，我们可以使用一个颜色数组 c o l o r color color，用来记录每个节点的颜色。初始时，所有节点的颜色都是未染色的（可以用 − 1 -1 −1 表示）。在 BFS 过程中，对于当前遍历到的节点 u u u，如果它没有被染色，则将其染成与其相邻节点的颜色相反的颜色，并将其入队列；如果它已经被染色，并且颜色与与其相邻节点的颜色相同，则说明给定的图不是二分图。最终，如果所有的节点都被染色了，并且没有相邻节点颜色相同的情况出现，则说明给定的图是二分图。
BFS 的时间复杂度为 O ( n + m ) O(n+m) O(n+m)，其中 n n n 表示节点数目， m m m 表示边数目。
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 100010, M = 2 * N;
int h[N], e[M], ne[M], idx;
int color[N]; // 用来记录每个节点的颜色，-1 表示未染色，0 表示染成红色，1 表示染成蓝色
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
bool bfs(int u)
{
queue<int> q;
q.push(u);
color[u] = 0;
while (q.size())
{
int t = q.front();
q.pop();
for (int i = h[t]; ~i; i = ne[i])
{
int j = e[i];
if (color[j] == -1)
{
color[j] = !color[t];
q.push(j);
}
else if (color[j] == color[t])
return false;
}
}
return true;
}
int main()
{
memset(h, -1, sizeof h);
int n, m;
cin >> n >> m;
while (m -- )
{
int a, b;
cin >> a >> b;
add(a, b), add(b, a);
}
bool flag = true;
memset(color, -1, sizeof color);
for (int i = 1; i <= n; i ++ )
if (color[i] == -1)
if (!bfs(i))
{
flag = false;
break;
}
if (flag) puts("Yes");
else puts("No");
return 0;
}