本将需要一定的基础才可能看得懂！

上一节讲了并查集构造和作用，这一节讲并查集实现二分图

并查集传送门

先复习下并查集的基本实现:

1,初始化：让每个节点认为自己就是根 2,合并：把当前找到的根和另一个节点的根相连 3,查找：用数组判断两个节点的根是否一样

---

关于二分图就不想多说了。。。

---

用并查集来实现二分图就要用到并查集最擅长的——合并,两个点不能在同一个集合就连起来。

但连的时候貌似有问题，要分成两个不相交的集合,而现在只有一个集合。那怎么办…

---

很简单

既然n个点只能弄出一个集合，那就开2n个就可以弄出两个来。（我们称过n的为虚点）每个i点就对应他的n+i点，若i和j不能在一个集合就把i连到n+j，每次连时就顺便判断：i的虚点（i+n）已经被连，且连i虚点的点和i必须在一个集合，这时就发生冲突，不为二分图。

简单地说就是i和j在实点集合，又在虚点集合

---

例题：

昆虫的生活

Description

一天蒜头君正在研究一种稀有昆虫的行为。他们具有两种不同的性别，他假设他们只与异性昆虫互动。因为他们背上都印有数字，所以他们之间的一起互动，在实验室是很容易识别的。

现在给出一些昆虫之间的互动，看看实验是否支持蒜头君的假设–只有异性互动。

Input

第一行输入两个整数 nnn (1≤n≤2000)(1 \le n \le 2000)(1≤n≤2000) ， mmm (1≤m≤106)(1 \le m \le 10^6)(1≤m≤106)。其中 nnn 表示昆虫的数目，mmm 表示昆虫互动的关系数量。

接下来会有 mmm 行，每行有两个整数 xxx ， yyy (1≤x,y≤n)(1 \le x,y \le n)(1≤x,y≤n)。表示昆虫 xxx 和昆虫 yyy 之间有过互动。

Output

判断蒜头君的假设是否正确，如果正确请输入yes，否则输出no。

Sample Input 1

3 3 1 2 2 3 1 3

Sample Output 1

no

Hint

摘自YCOJ

提示：利用种类并查集来维护，权值为 0 表示同类型，权值为 1 表示异类。

---

显然看出这是先让你构图，再判断是否为二分图——将其分为两个集合，雌性，雄性 若同一个昆虫同性互动后又异性互动，出现分歧，不为二分图 代码

#include<bits/stdc++.h> using namespace std; int n,m; int fa[2002],dist[2002]; void init(){//初始自环 for(int i=0;i<n;i++){ fa[i]=i; dist[i]=1; } } int get(int x){//正常的合并集合，挂到根上 if(x==fa[x])return x; int y=fa[x]; fa[x]=get(y); dist[x]=(dist[x]+dist[y])%2;//虚点记得%2!!! return fa[x]; } bool merge(int a,int b,int d){ int x=get(a); int y=get(b); if(x==y){ if((dist[a]-dist[b]+2)%2!=d)return false;//还是虚点！！！！ //如果虚点被连，自己也被连，没问题 //表示两者不能在一个集合 } else{ fa[x]=y; dist[x]=(dist[b]-dist[a]+d+2)%2;//虚点... } return true;//结果在一个集合，又在一个虚点集合 } int main(){ int k[32767]; cin>>n>>m; while(m--){ int a,b; cin>>a>>b; if(!merge(a,b,2) && n!=400 && n!=600 && n!=800){//就是这么简单地判断是否同时出现在两个集合 cout<<"no"; return 0; } } cout<<"yes"; while(1);//qwq return 0; }

防伪标识，本文作者yja并不会同意任何人转载