「理论上到现在应该已经学习完了所有 NOIP 考纲内的知识点，如果还有不会的赶紧学习。」

突然发现自己从来没有学过二分图。想起来去年本来想学，但是看了一下好像没怎么考，学别的去了。

二分图基础

定义

对于一张图，如果其点集可以划分为两个部分，且图上的每一条边的两个端点都不在同一个部分中，则称这个图为「二分图」。

形式化地，设图 $G=(V,E)$，若 $V=X\cup Y,X\cap Y=\varnothing$，则对于 $\forall (u,v)\in E$ 有 $u\in X,v\in Y$，则 $G$ 为二分图。

常见的二分图有：树、偶环、网格。

如果已知 $G=(V,E),V=X\cap Y,X\cap Y=\varnothing$，则二分图 $G$ 也可记作 $G=(X,Y,E)$。称 $X,Y$ 分别为 $G$ 的左部、右部。

性质

1. 二分图可以仅用两种颜色对所有节点染色，且没有边连接颜色相同的点。
2. 二分图中不存在奇环。
3. 二分图的各连通块互不影响。

性质 $1$ 是显然的，且性质 $1$ 与二分图的定义等价。

对于性质 $2$，考虑奇环不满足性质 $1$。

判定

常用的判定方法有：

1. 可以仅用两种颜色对所有节点染色，且没有边连接颜色相同的点的图为二分图。
2. 不存在奇环的图为二分图。

判定方法 $1$ 与定义等价。

对于判定方法 $2$，考虑到原图要么是树，要么是含有偶环的图。前者是二分图，而后者也是，因为将偶环缩为一个点不影响其是否为二分图，则等价于一棵树。

实际应用中，就常常通过在图上染色的方式来判定二分图——间隔染色，如果当前节点 $x$ 应该染的颜色 $\textit{color}$ 与之前染的颜色 $\textit{vis}_x$ 不同，则不为二分图。

SP3377 BUGLIFE - A Bug’s Life

虫子还有同性恋。

给定 $n$ 个点，$m$ 条边，求能否将所有节点划分为两个部分，使得所有边连接的节点都处于不同部分，多测。如果可以，输出 No suspicious bugs found!，否则输出 Suspicious bugs found!。

显然是二分图判定问题。注意要对所有连通块进行 DFS 判断。时间复杂度 $\mathcal O(n+m)$。

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
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
constexpr const int N=2000,M=1e6;
int n;
vector<int>g[N+1];
int vis[N+1];
void dfs(int x,int fx,int color,bool &ans){
	if(vis[x]){
		if(vis[x]!=color){
			ans=true;
		}
		return;
	}
	vis[x]=color;
	for(int i:g[x]){
		if(i==fx){
			continue;
		}
		dfs(i,x,color^3,ans);
		if(ans){
			return;
		}
	}
}
int main(){
	/*freopen("test.in","r",stdin);
	freopen("test.out","w",stdout);*/
	
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	int T;
	cin>>T;
	for(int i=1;i<=T;i++){
		int m;
		cin>>n>>m;
		for(int i=1;i<=n;i++){
			g[i].resize(0);
		}
		while(m--){
			int u,v;
			cin>>u>>v;
			g[u].push_back(v);
			g[v].push_back(u);
		}
		bool ans=false;
		memset(vis,0,sizeof(vis));
		for(int i=1;i<=n;i++){
			if(!vis[i]){
				dfs(i,0,1,ans);
			}
		}
		cout<<"Scenario #"<<i<<":\n";
		if(ans){
			cout<<"Suspicious bugs found!\n";
		}else{
			cout<<"No suspicious bugs found!\n";
		}
	}
	
	cout.flush();
	
	/*fclose(stdin);
	fclose(stdout);*/
	return 0;
}

二分图最大匹配

匈牙利算法

二分图算法怎么那么多名字。也可以叫 Kuhn 算法，实际上，Kuhn 算法是匈牙利算法的一部分。

对于一个匹配，引入概念：

• 交错路（alternating path）：匹配边、非匹配边交错形成的路径。
• 增广路（augmenting path）：两端为非匹配点的交错路。

考虑一条增广路，对其进行增广操作，即将增广路上的匹配边与非匹配边交换，则可以增加 $1$ 条匹配边。

考虑不断进行增广操作，则不能增广的时候为最大匹配。

因此可以枚举左部点 $u$，令其和与其相连的右部点 $v$ 配对（边 $(u,v)$ 存在）：

• 如果 $v$ 已经配对了，就尝试让与之配对的 $u’$ 换一个点 $v’$ 配对：
  • 如果找到了合法 $v’$，那么 $u,v$ 配对，可以进行增广操作。
  • 找不到，则 $v$ 不能与 $u$ 配对。
• 如果 $v$ 没有配对，自然最好，$u,v$ 配对。

时间复杂度：$\mathcal O(nm)$，$n$ 为左部点数（总点数），$m$ 为边数。

luogu P3386 【模板】二分图最大匹配

给定一个二分图，其左部点的个数为 $n$，右部点的个数为 $m$，边数为 $e$，求其最大匹配的边数。

左部点从 $1$ 至 $n$ 编号，右部点从 $1$ 至 $m$ 编号。

• Previous
  题解：[BalticOI 2018] 基因工程
• Next
  Vercel 部署后通过Cloudflare代理导致重定向次数过多的解决方案