什么叫二分图

  • 有两顶点集且图中每条边的的两个顶点分别位于两个顶点集中，每个顶点集中没有边直接相连接！

  • 说人话的定义：图中点通过移动能分成左右两部分，左侧的点只和右侧的点相连，右侧的点只和左侧的点相连。

  • 下图就是个二分图：

二分图 -w150

  • 下图不是个二分图：

1.png

如果判断一个图是不是二分图？

  • 开始对任意一未染色的顶点染色。

  • 判断其相邻的顶点中，若未染色则将其染上和相邻顶点不同的颜色。

  • 若已经染色且颜色和相邻顶点的颜色相同则说明不是二分图，若颜色不同则继续判断。

  • bfs和dfs可以搞定！

20230723与y总代码模板不同，为自己独立实现，不够美观，但便于自己理解

debug过程：

  • 需要注意到本题是无向图，所以add函数需要用两次，还有就是我们使用链式前向星结构去存图，所以ne和e数组需要开两倍的边数。
就是因为数组开小了，导致最后tle了，数组开小了什么报错都有可能出现
  • 染色算法能够解决非连通图的二部图判定，所以从一个点dfs出发是不够的，要多源dfs
    也就是说对每个连通块进行dfs,先对一个点dfs后，找此时没有被染色的点再dfs，直到全都被染色或者dfs过程中return false;
  • 这个dfs过程不需要还原现场，因为我们需要保留所有点的颜色。
  • 我的代码中dfs函数只有一个参数，yxc的代码是两个参数，都是可以的？！
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <bits/stdc++.h>
using namespace std;
//# define int long long
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int>pii;

const int N =1e5+10;
const int M=2e5+10;
const int inf=0x3f3f3f3f;
const int mod=998244353;

//int a[N];

int n, m;
int h[N],ne[M],e[M],idx;
bool st[N];
int color[N];
void add(int a,int b){
e[idx]=b;
ne[idx]=h[a];
h[a]=idx++;
}
bool dfs(int u){
    
for(int i=h[u];i!=-1;i=ne[i]){
    int j=e[i];
    if(!color[j]){
            color[j]=3-color[u];
        if(!dfs(j)){
            return false;
        }
    }
    else {
        if(color[j]!=3-color[u])return false;
    }
}

return true;
}

int main(){

cin.tie(0);cout.tie(0);
ios::sync_with_stdio(false);
memset(h,-1,sizeof h);
int t;
t=1;
//cin>>t;
while(t--){
     cin>>n>>m;
     for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        add(u,v);
        add(v,u);
     }

}
bool flag=true;

for(int i=1;i<=n;i++){
    if(!color[i]){
        color[i]=1;
        if(!dfs(i)){
            flag=false;
        }
    }
}
if(flag)cout<<"Yes";
else cout<<"No";
return 0;

}


双参数版的代码

dfs的含义：将u这个点染成c颜色后，返回值是表示会不会出现冲突

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <bits/stdc++.h>
using namespace std;
//# define int long long
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int>pii;

const int N =1e5+10;
const int M=2e5+10;
const int inf=0x3f3f3f3f;
const int mod=998244353;

//int a[N];

int n, m;
int h[N],ne[M],e[M],idx;
bool st[N];
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;
for(int i=h[u];i!=-1;i=ne[i]){
    int j=e[i];
    if(color[j]==0){
        if(dfs(j,3-c)==false)return false;
    }
    else {
        if(color[j]==c)return false;
    }
}
return true;
}


int main(){

cin.tie(0);cout.tie(0);
ios::sync_with_stdio(false);
memset(h,-1,sizeof h);
int t;
t=1;
//cin>>t;
while(t--){
     cin>>n>>m;
     for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        add(u,v);
        add(v,u);
     }

}
bool flag=true;

for(int i=1;i<=n;i++){
    if(!color[i]){
        if(dfs(i,1)==false){
            flag=false;
        }
    }
}
if(flag)cout<<"Yes";
else cout<<"No";
return 0;

}