染色法判别二分图 —— 模板题 AcWing 860. 染色法判定二分图

时间复杂度是 O(n+m)O(n+m), nn 表示点数，mm 表示边数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
bool dfs(int u,int c){//判断存在奇环，存在返回true
  color[u]=c;
  for(auto v:e[u]){
   
    if(!color[v]){
      if(dfs(v,3-c))return 1;
    }
    else if(color[v]==c)return 1;//有奇环
  }
  return 0;
}
bool check()
{//判断是不是二分图
    fill(color,color+1+n,0);
    bool flag = true;
    for (int i = 1; i <= n; i ++ )//可能图不连通
        if (!color[i] )
            if (dfs(i, 1))//有奇环就不是二分图
            {
                flag = false;
                break;
            }
    return flag;
}

匈牙利算法 —— 模板题 AcWing 861. 二分图的最大匹配

时间复杂度是 O(nm)O(nm), nn 表示点数，mm 表示边数
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
int ans=0;
vector<int>e[N];
int vis[N],match[N];
bool dfs(int u){
  for(auto v:e[u]){
    //妹子的编号v
    if(vis[v]) continue;
    vis[v]=1; //先标记这个妹子
    if(!match[v]||dfs(match[v])){
      match[v]=u; //配成对
      return 1;
    }
  }
  return 0;
}
void solve(){
	int k;
	cin>>n>>m>>k;
	for(int i=1;i<=k;i++){
		int u,v;cin>>u>>v;
		e[u].push_back(v);
	}
	for(int i=1;i<=n;i++){
		fill(vis,vis+m+1,0);//每轮找增广路以前清空vis
		if(dfs(i))ans++;
	}
	cout<<ans;
}