染色法判断是否是二分图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
bool dfs(int x) {
    for (int y : g[x]) {
        if (col[y]) {
            if (col[y] == col[x]) return 0;
        } else {
            col[y] = 3 - col[x];
            if(!dfs(y)) return 0;
        }
    }
    return 1;
}

int main() {
    ...//输入 输出 建边等
    for (int i = 1; i <= n; i++){
        if (!col[i]) {
            col[i] = 1;
            dfs(i);
        }
    }
}

二分图最大匹配

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
bool dfs(int x) {
    for (int y : g[x]) {
        if (!v[y]) {
            v[y] = 1;
            if (!match[y] || dfs(match[y])) {
                match[y] = x;
                return 1;
            }
        }
    }
    return 0;
}

int main() {
	...// 建边
    
	// 从左边每个点开始，看能不能找到一条增广路
	int ans = 0;	// ans 为最大匹配数
    for (int i = 1; i <= n; i++) {	// 遍历左部图的每个点
        memset(v, 0, sizeof v);
        if (dfs(i)) ans++;
    }
}

练习题

题目 类型
【模板】二分图最大匹配 二分图最大匹配【模板】
棋盘覆盖 二分图最大匹配
車的放置 二分图最大匹配
阻止城堡 二分图最大匹配