二分图基础

什么是二分图：

二分图也叫二部图，设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为一个二分图，如下图所有的顶点可以分成A，B两个集合，而A集合与B集合中的点与自己的阵营的点是没有连线的（A集合的点只与B集合的点有边相连），则称这个为一个二分图

二分图的判定（染色法）：

给定一个(n)个点(m)条边的无向图，图中可能存在重编和自环。请判断这个图是否为二分图，数据范围：(1leq n,mleq 10^{5})

算法描述：

选取一个未染色的点u进行染色
遍历u的相邻节点v：若v未染色，则染色成与u不同的颜色，并对v重复第2步；若v已经染色，如果 u和v颜色相同，判定不可行退出遍历。
若所有节点均已染色，则判定可行。

(dfs)版模板：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 #define endl '
'
 5 const int mod=1e9+7;
 6 const int maxn=1e5+10;
 7 
 8 struct node{
 9     int to,nxt;
10 }e[maxn<<1];
11 
12 int head[maxn],tot;
13 int n,m;
14 bool flag;
15 int color[maxn];
16 
17 void init(){
18     memset(head,-1,sizeof(head));
19     tot=0;
20     flag=true;
21 }
22 
23 void addedge(int u,int v){
24     e[tot].to=v; e[tot].nxt=head[u]; head[u]=tot++;
25     e[tot].to=u; e[tot].nxt=head[v]; head[v]=tot++;
26 }
27 
28 bool dfs(int u,int c){
29     color[u]=c;                     //给当前这个点u的颜色是c
30     for(int i=head[u];~i;i=e[i].nxt){
31         int to=e[i].to;
32         if( !flag ){
33             return false;
34         }else if( !color[to] ){     //u 的邻接点 to 未被染色
35             dfs(to,3-c);            //u的颜色如果是1，to就是3-1=2；u的颜色如果是2，to就是3-2=1
36         }else if( color[to]==c ){
37             return flag=false;
38         }
39     }
40     return true;
41 }
42 
43 int main()
44 {
45     init();
46     cin>>n>>m;
47 
48     while( m-- ){
49         int a,b; cin>>a>>b;
50         addedge(a,b);
51     }
52     for(int i=1;i<=n;i++){          //遍历图的所有点
53         if( !color[i] ){
54             if( !dfs(i,1) ){
55                 flag=false;
56                 break;
57             }
58         }
59     }
60     if( flag ) cout<<"Yes"<<endl;   //是二分图
61     else cout<<"NO"<<endl;          //不是二分图
62 }

(bfs)版模板：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 #define endl '
'
 5 const int mod=1e9+7;
 6 const int maxn=1e5+10;
 7 
 8 struct node{
 9     int to,nxt;
10 }e[maxn<<1];
11 
12 int head[maxn],tot;
13 int n,m;
14 bool flag;
15 int color[maxn];
16 
17 void init(){
18     memset(head,-1,sizeof(head));
19     tot=0;
20     flag=true;
21 }
22 
23 void addedge(int u,int v){
24     e[tot].to=v; e[tot].nxt=head[u]; head[u]=tot++;
25     e[tot].to=u; e[tot].nxt=head[v]; head[v]=tot++;
26 }
27 
28 bool bfs(int u){
29     queue<pair<int,int>>q;
30     q.push({u,1});//first:存节点编号,second存节点颜色
31     color[u]=1;
32     while( !q.empty()){
33         pair<int,int> t=q.front(); q.pop();
34         int ver=t.first,c=t.second;
35         for(int i=head[ver];~i;i=e[i].nxt){
36             int to=e[i].to;
37             if( !color[to] ){
38                 color[to]=3-c;
39                 q.push({to,3-c});
40             }else if( color[to]==c ) return false;
41         }
42     }
43     return true;
44 }
45 
46 int main()
47 {
48     init();
49     cin>>n>>m;
50 
51     while( m-- ){
52         int a,b; cin>>a>>b;
53         addedge(a,b);
54     }
55     for(int i=1;i<=n;i++){          //遍历图的所有点
56         if( !color[i] ){
57             if( !bfs(i) ){
58                 flag=false;
59                 break;
60             }
61         }
62     }
63     if( flag ) cout<<"Yes"<<endl;   //是二分图
64     else cout<<"NO"<<endl;          //不是二分图
65 }

模板题：二分图一•二分图判定