二分图基础知识

前言：总结一下二分图相关的知识点

0X00 基础

• 判断是不是二分图

785. 判断二分图

DFS 遍历所有节点，遍历一个节点就给一个节点上色。如果颜色冲突了，就不是二分图。

class Solution:
    def isBipartite(self, g: List[List[int]]) -> bool:
        n, col = len(g), [0] * len(g)
        def dfs(n, c):
            if col[n] == c: return False
            elif col[n] == c ^ 1: return True
            col[n] = c ^ 1
            for i in g[n]:
                if not dfs(i, c ^ 1): return False
            return True
        
        for i in range(n):
            if col[i]: continue
            if not dfs(i, 2): return False
        
        return True

时间复杂度：

• 匈牙利算法（二分图的最大匹配）

861. 二分图的最大匹配

匈牙利算法是一个比较简单且高效的算法。时间复杂度：

核心思想是：每次去寻找和这个点能够匹配的点：

• 如果另一点已经匹配了，就尝试重新匹配另外点的匹配点
• 没有匹配就暂时选择它

from sys import stdin

def read():
    return list(map(int, stdin.readline().split()))

def find(u):
    for i in g[u]:
        if not st[i]:
            st[i] = True
            if not match[i] or find(match[i]):
                match[i] = u
                return True
    return False

n1, n2, ne = read()
g = [[] for _ in range(1+n1)]

for _ in range(ne):
    a, b = read()
    g[a].append(b)

match = [0] * (1+n2)
res = 0
for i in range(1, n1+1):
    st = [False] * (1+n2)
    if find(i):
        res += 1
print(res)

0X01 进阶

上面只是一些基础知识，后面再总结进阶的题目