【二分图】判断二分图
2020-07-15 14:43:00 # ACM

染色法

学习自详解1 ,详解2

例题 1

POJ 2492 “A Bug’s Life”

解: 判断是否为二分图即可 ,同时可能有多个连通图 ,需要多次搜索染色 .

示例代码 1

说明: 邻接矩阵存图 ,$dfs$搜索染色 .

时间 $4704MS$ … 题目给了$10000MS$ 管他呢 .

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
//#include <bits/stdc++.h>
#include <stdio.h>
#include <string.h>
#include <iostream>
#define LL long long
#define Pi acos(-1.0)
#define INF 2147483646
#define eps 1e-9
#define MS 2009
#define mss 17
using namespace std;
// Notice the data size
// Notice the input and output 

int n,m,k,u,v,flag;
int mp[MS][MS];
int col[MS];

void dfs(int bt){
	if(flag) return;
	for(int i=1;i<=n;i++){
		if(mp[bt][i]){
			if(col[i] == col[bt]){
				flag = 1;
				return;
			}
			else if(col[i] == -1){
				col[i] = !col[bt];
				dfs(i);
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin >> k;
	for(int o=1;o<=k;o++){
		memset(mp,0,sizeof mp);
		memset(col,-1,sizeof col);
		flag = 0;
		cin >> n >> m;
		for(int i=1;i<=m;i++){
			cin >> u >> v;
			mp[u][v] = mp[v][u] = 1;
		}
		for(int i=1;i<=n;i++){
			if(col[i] == -1){
				col[i] = 0;
				dfs(i);
			}
		}
		if(flag){
			cout << "Scenario #" << o << ":" << endl;
			cout << "Suspicious bugs found!" << endl;
			cout << endl;
		}
		else{
			cout << "Scenario #" << o << ":" << endl;
			cout << "No suspicious bugs found!" << endl;
			cout << endl;
		}
	}
		
	return 0; 
}

示例代码 2

说明: 链式前向星存图 ,$dfs$搜索染色 .

时间 $4407MS$… 和邻接矩阵差不了多少 ,就当再练一次吧 .

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
77
78
//#include <bits/stdc++.h>
#include <stdio.h>
#include <iostream>
#define LL long long
#define Pi acos(-1.0)
#define INF 2147483646
#define eps 1e-9
#define MS 2009
#define mss 17
using namespace std;
// Notice the data size
// Notice the input and output 

int n,m,k,u,v,flag,tot;
int col[MS];
struct node{
	int to,ne;
}edge[2000009];
int head[MS];

void add(int u,int v){
	edge[tot].to = v;
	edge[tot].ne = head[u];
	head[u] = tot++;
}

void dfs(int bt){
	if(flag) return;
	for(int i=head[bt];i!=-1;i=edge[i].ne){
		int it = edge[i].to;
		if(col[it] == col[bt]){
			flag = 1;
			return;
		}
		else if(col[it] == -1){
			col[it] = !col[bt];
			dfs(it);
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin >> k;
	for(int o=1;o<=k;o++){
		for(int i=0;i<MS;i++) col[i] = head[i] = -1;
		flag = tot = 0;
		cin >> n >> m;
		for(int i=1;i<=m;i++){
			cin >> u >> v;
			add(u,v);
			add(v,u);
		}
		for(int i=1;i<=n;i++){
			if(col[i] == -1){
				col[i] = 0;
				dfs(i);
			}
		}
		if(flag){
			cout << "Scenario #" << o << ":" << endl;
			cout << "Suspicious bugs found!" << endl;
			cout << endl;
		}
		else{
			cout << "Scenario #" << o << ":" << endl;
			cout << "No suspicious bugs found!" << endl;
			cout << endl;
		}
	}
		
	
	
	
	
	return 0; 
}

例题 2

cf 1093D “Beautiful Graph”

题意: k 组样例 ,每次给出 n 个顶点 m 条边的无向图 ,将整个图的所有顶点填充数字 ,每个顶点 u 可填数字 1，2，3 . 要求 m 条边每条边连接的两个顶点 (u,v) 的填充的数字权值之和为奇数 .问这样的填充方法有多少个 .方案可能很大，取模$998244353$ .

如果没有则输出$0$.

解: 先将其分为二分图 ,得到两个集合 $X$ ,$Y$ ,当 $X$ 中填 $2$ 此时 $Y$ 中每个点都有 $1$ $3$ 两种选择 ,所以有 $2^y$ 种 . 反过来 $Y$ 填 $2$ 则有 $2^x$ 种 ,所以每一个连通图都有 $2^x + 2^y$ 种 . 可能出现多个连通图 ,累乘即可 .

注意要对 $2$ 的次方作打表处理 ,当时傻傻的用快速幂超时 …

示例代码

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
77
78
79
80
81
#include <bits/stdc++.h>
#define LL long long
#define Pi acos(-1.0)
#define INF 2147483646
#define eps 1e-9
#define MS 300009
#define mss 17
#define mod 998244353
using namespace std;
// Notice the data size
// Notice the input and output 

LL n,m,k,u,v,flag,cx,cy;
LL col[MS],er[MS];

struct node{
	LL to,ne;
}edge[MS<<1];
LL head[MS],tc;

void add(LL a,LL b){
	edge[tc].to = b;
	edge[tc].ne = head[a];
	head[a] = tc++; 
}

void dfs(LL bt,LL cc){ // bfs也行
	if(flag) return;
	for(int i=head[bt];i!=-1;i=edge[i].ne){
		LL tt = edge[i].to;
		if(col[tt] == col[bt]){
			flag = 1;
			return;
		}
		else if(col[tt] == -1){
			col[tt] = !cc;
			if(col[tt] == 0) cx++; // x 集合元素个数++ 
			else cy++; // y 集合元素个数++ 
			dfs(tt,!cc);
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	er[0] = 1;
	for(int i=1;i<MS;i++){ // 2 的次方 
		er[i] = er[i-1]*2LL%mod;
	}
	cin >> k;
	while(k--){
		flag = 0;
		LL ans = 1;
		cin >> n >> m;
		for(int i=0;i<=n;i++){
			head[i] = col[i] = -1;
		}
		for(int i=1;i<=m;i++){ // 链式前向星 
			cin >> u >> v;
			add(u,v);
			add(v,u);
		}
		
		for(int i=1;i<=n;i++){ // 也许有多个连通图 
			if(col[i] == -1){
				cx = cy = 0;
				cx++; // 记录 X 集合元素个数 
				col[i] = 0;
				dfs(i,0);
				if(flag) break;
				ans = ans*(er[cx]+er[cy])%mod;
			}
		}
		
		if(flag) cout << 0 << endl;
		else cout << ans << endl;
	}
	
	return 0; 
}

Prev
2020-07-15 14:43:00 # ACM
Next