二分图的判定&最大匹配

如果一张无向图的N个结点可以分成A,B两个非空集合，其中$A\cap B=\varnothing$，并且在同一集合内的点之间都没有边相连，则称这张图为二分图。

二分图判定

定理：一张图是二分图，当且仅当图中不存在奇环（长度为奇数的环）。

P1330 封锁阳光大学

染色法判定：尝试用黑白两色标记，当一个结点被标记后，它的所有相邻结点应该被标记与之相反的颜色，若该标记过程中出现冲突，则说明图中存在奇环。

下用BFS、DFS、并查集分别实现。

BFS

#include
using namespace std;
const int N=1e4+10,M=2e5+10;
int head[N],ver[M],nex[M],vis[N];
int n,m,u,v,tot=0,ok=1;
int sum[5],ans;

void add(int u,int v)
{
	ver[++tot]=v;
	nex[tot]=head[u];
	head[u]=tot;
}

bool bfs(int start,int color)
{
	queue<int>q;
	q.push(start);
	vis[start]=color;
	//printf("vis[%d]=%d\n",start,vis[start]);
	sum[1]=1,sum[2]=0;//初始化
	while(q.size())
	{
		int now=q.front();
		q.pop();
		for(int i=head[now];i;i=nex[i])
		{
			int to=ver[i];
			if(vis[to]==0) 
			{
				if(vis[now]==1) vis[to]=2,sum[2]++;
				else vis[to]=1,sum[1]++;
				//printf("vis[%d]=%d\n",to,vis[to]);
				q.push(to);
			}
			else if(vis[to]==vis[now]) return false;
		}
	}
	return true;
}

int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&u,&v);
		add(u,v),add(v,u);
	}
	for(int i=1;i<=n;i++)
	{
		if(vis[i]) continue;//vis[i]==0的话表明跟之前的结点都不连通 
		if(!bfs(i,1))
		{
			ok=0;
			break;
		}
		else ans+=min(sum[1],sum[2]);//加和
	}
	if(ok) cout<<ans<<endl;
	else cout<<"Impossible"<<endl;
	return 0;
}
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

DFS

#include
using namespace std;
const int N=1e4+10,M=2e5+10;
int head[N],ver[M],nex[M],vis[N];
int n,m,u,v,tot=0,ok=1;
int sum[5],ans;

void add(int u,int v)
{
	ver[++tot]=v;
	nex[tot]=head[u];
	head[u]=tot;
}

bool dfs(int now,int color)
{
	for(int i=head[now];i;i=nex[i])
	{
		int to=ver[i];
		if(!vis[to]) 
		{
			if(vis[now]==1) vis[to]=2,sum[2]++;
			else vis[to]=1,sum[1]++;
			dfs(to,vis[to]);
		}
		else if(vis[to]==vis[now]) return false;
	}
	return true;
}


int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&u,&v);
		add(u,v),add(v,u);
	}
	for(int i=1;i<=n;i++)
	{
		if(vis[i]) continue;//vis[i]==0的话表明跟之前的结点都不连通 
		sum[1]=1,sum[2]=0;
		vis[i]=1;
		if(!dfs(i,1))
		{
			ok=0;
			break;
		}
		else ans+=min(sum[1],sum[2]);//加和
	}
	if(ok) cout<<ans<<endl;
	else cout<<"Impossible"<<endl;
	return 0;
}
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

并查集二分图的判定（“扩展域”的并查集）：

#include
using namespace std;
const int N=1e4+10,M=2e5+10;
int f[N*2],size[N];
int n,m,x,y,tot=0,ok=1;

int find(int x)
{
	if(f[x]==x) return f[x];
	else return f[x]=find(f[x]);
}

int main()
{
	cin>>n>>m;
	for(int i=1;i<=2*n;i++)
		f[i]=i;
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&x,&y);
		int fx1=find(x),fy1=find(y);
		int fx2=find(x+n),fy2=find(y+n);
		if(fx1==fy1)
		{
			ok=0;
			break;
		}
		else f[fx2]=fy1,f[fy2]=fx1;
	}
	if(ok) cout<<"OK"<<endl;
	else cout<<"Impossible"<<endl;
	return 0;
}
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

#include
using namespace std;
const int N=1e4+10,M=2e5+10;
int f[N*2],size[N*2],mem[N*2],h[N];
//1~n白染色域，n+1~2n黑染色域 
int n,m,x,y,tot=0,ok=1,ans;

int find(int x)
{
	if(f[x]==x) return f[x];
	else return f[x]=find(f[x]);
}
void merge(int x,int y)
{
    int fx=find(x);
    if(fx!=y)
    {
        f[y]=fx;
        size[fx]+=size[y];
    }
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		f[i]=i,size[i]=1;
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&x,&y);
		//每条边的两个顶点必不在一个染色域 
		int fx=find(x),fy=find(y);
		if(fx==fy)//在同一个染色域 
		{
			cout<<"Impossible"<<endl;
			return 0;
		}
		else
		{
			if(h[x]) merge(h[x],fy);
			if(h[y]) merge(h[y],fx);
			h[x]=fy,h[y]=fx;
		}
	}
	for(int i=1;i<=n;i++)
	{
		int q=find(i);
		if(!mem[q])//一个未处理过的并查集 
		{
			int p=find(h[i]);
			mem[p]=mem[q]=1;
			ans+=min(size[p],size[q]);//两域取其小 
		}
	}
	cout<<ans<<endl;
	return 0;
}
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

二分图最大匹配

匈牙利算法（增广路算法）：

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

尝试给每个左部结点x匹配一个右部结点y。y能与x匹配的条件：

1. y本身就是非匹配点；
2. y已经与x’匹配，但从x’出发能找到另一个y’与x’匹配。

特点：当一个结点成为匹配点之后，至多因为找到增广路而更换匹配对象，但是不会变回非匹配点。

#include
using namespace std;
const int N=520;
int n,m,e,tot,ans;
int mp[N][N],vis[N],match[N];

bool dfs(int x)
{
	for(int i=1;i<=m;i++)
	{
		if(!mp[x][i]||vis[i]) continue;
		vis[i]=1;
		if(!match[i]||dfs(match[i]))
		{
			match[i]=x;
			return true;
		}
	}
	return false;
}

int main()
{
	cin>>n>>m>>e;
	for(int i=1;i<=e;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		mp[x][y]=1;
	}
	for(int i=1;i<=n;i++)
	{
		memset(vis,0,sizeof(vis));
		if(dfs(i)) ans++;
	}
	cout<<ans;
}

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