【题目来源】
【题目描述】
给定一个 n 个点 m 条边的无向图，图中可能存在重边和自环。
请你判断这个图是否是二分图。
【输入格式】
第一行包含两个整数 n 和 m。
接下来 m 行，每行包含两个整数 u 和 v，表示点 u 和点 v 之间存在一条边。
【输出格式】
如果给定图是二分图，则输出 Yes，否则输出 No。
【输入样例】
4 4
1 3
1 4
2 3
2 4
【输出样例】
Yes
【数据范围】
1≤n,m≤10^5
【算法分析】
● 二分图的基本性质
（1）二分图要求所有边连接的两个节点必须属于不同的集合。
（2）与同一节点相邻的所有节点必须属于同一集合（即二分图的另一部分）。
● 基于并查集实现的算法核心步骤详解
对于每个节点 u 遍历其所有邻居 j：
（1）冲突检测：如果 u 和 j 已在同一集合，即 find(u)==find(j)。说明存在奇数环，不是二分图。
（2）邻居合并：将 u 的所有邻居合并到同一集合，即 pre[find(e[h[u]])]=find(j)。确保它们都在二分图的另一侧。
基于并查集算法的优势在于避免了递归深度问题，适合处理大规模图，且代码简洁高效。整体复杂度 O(n+m)。
【算法代码】
#include <bits/stdc++.h>
using namespace std;const int N=1e5+5;
int pre[N];
int e[N<<1],ne[N<<1],h[N],idx;void add(int a,int b) {e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}int find(int x) {if(x!=pre[x]) pre[x]=find(pre[x]);return pre[x];
}int main() {int n,m;cin>>n>>m;memset(h,-1,sizeof h);for(int i=1; i<=n; i++) pre[i]=i;while(m--) {int a,b;cin>>a>>b;add(a,b),add(b,a);}for(int u=1; u<=n; u++) {for(int i=h[u]; i!=-1; i=ne[i]) {int j=e[i];if(find(j)==find(u)) {cout<<"No\n";return 0;}pre[find(e[h[u]])]=find(j);}}cout<<"Yes\n";return 0;
}/*
in:
4 4
1 3
1 4
2 3
2 4out:
Yes
*/
【参考文献】