二分图

GitHub跳转原题关系图返回列表

先求最大匹配,再在按匹配边定向的交错图上用强连通分量与自由点可达性判定每条边是否属于某个大小为 n 的匹配。

OJ: roj

题目 ID: 1730

难度:提高+/省选-

标签:二分图匹配Hopcroft-Karp强连通分量python

创建: 2026-10-07 19:03

更新: 2026-10-07 19:03

形式化题目

给定一个二分图 G=(L,R,E)G = (L, R, E),其中 ∣L∣=n|L| = n、∣R∣=m|R| = m,且保证 n⩽mn \leqslant m。对每一条边 e∈Ee \in E,判定:原图中是否存在一个大小为 nn(即饱和整个左部)的匹配 MM 满足 e∈Me \in M。

输出一个 n×mn \times m 的 0/1 矩阵:若左部点 ii 与右部点 jj 之间不存在边,或存在边但没有任何大小为 nn 的匹配包含它,则第 ii 行第 jj 列为 1;否则为 0。也就是说输出是判定结果的取反:0 才表示"这条边可用"。

约束:1⩽n⩽3001 \leqslant n \leqslant 300,1⩽m⩽15001 \leqslant m \leqslant 1500,n⩽mn \leqslant m。

注意 n⩽mn \leqslant m 是关键前提——它保证了"饱和左部的大小为 nn 的匹配"总是左部完美匹配:每个左部点都必须被匹配,而右部点允许有剩余。因此本题问的是"每条边能否作为左部完美匹配的一条边",而不是笼统的"最大匹配的边"。

正解

思路

先排除无解情形。 如果最大匹配的大小 <n< n,那么一个大小为 nn 的匹配根本不存在,所有格子都输出 1。这一步用 Hopcroft-Karp 在 O(EV)O(E\sqrt{V}) 内求出最大匹配即可,同时得到一个匹配 MM(若存在大小为 nn 的匹配,则 ∣M∣=n|M| = n,它饱和左部)。

难点在第二步:有了一个匹配,怎么判断别的边。 朴素的"逐条边删掉再求一次最大匹配"是 O(nm⋅EV)O(nm \cdot E\sqrt{V}),nm=4.5×105n m = 4.5 \times 10^5,绝对不可行。必须一次性地把所有边分类。

关键观察是交错路/交错环的翻转:若 MM 是一个左部完美匹配,M′M' 是另一个,则对称差 M△M′M \triangle M' 由若干条交错路与交错环组成,其中交错路的两端必然都在"两个匹配都没盖住"的点上。由于两个匹配都饱和左部,两端就只能是右部的自由点(MM 未匹配的右部点,共有 m−nm - n 个,可能为 0)。于是:

  • 若 ee 同时属于某个交错环 CC(在 CC 上把匹配与非匹配边互换,得到的新匹配大小不变,仍饱和左部),则 ee 可用;
  • 若 ee 位于某条从右部自由点出发的交错路上,则沿这条路径翻转前缀(或整条路径)也能把 ee 变成匹配边,且匹配大小不变,仍饱和左部。

这两条覆盖了全部情形,也正是经典的"边属于某个最大匹配"判定的两条判据。

把这两条判据变成图上可达性。 按 MM 定向建交错有向图 DD:顶点是全部 n+mn + m 个点;匹配边 uu-vv 建成弧 u→vu \to v(左 →\to 右),非匹配边 uu-vv 建成弧 v→uv \to u(右 →\to 左)。在这个定向下,从右部点出发的"交错路"恰好是 DD 中的有向路(右部点先沿非匹配边走到左部点,再沿匹配边走到右部点,交替进行)。于是:

  • 条件 (a):uu 与 vv 在 DD 的同一个强连通分量里   ⟺  \iff 该边落在一条交错环上。用 Tarjan(或 Kosaraju)一次求出所有 SCC。
  • 条件 (b):vv 在 DD 中从某个 MM 未匹配的右部点可达。把所有右部自由点作为源做一次 BFS/DFS 即可。

匹配边本身当然属于 MM,恒输出 0。

用样例 1 直观感受一下 DD 的形状。图是 4×44 \times 4:第 2 行只有一条边到右部点 1,所以任何左部完美匹配都必须含 (2,1)(2,1);右部点 1 因此被锁死不能再用。本仓库程序实测 Hopcroft-Karp 给出 M={(1,2),(2,1),(3,4),(4,3)}M = \{(1,2), (2,1), (3,4), (4,3)\}(n=m=4n = m = 4,没有右部自由点,条件 (b) 在本样例中不会触发),此时交错有向图 DD 中 {L1,L3,L4,R2,R3,R4}\{L1, L3, L4, R2, R3, R4\} 因 L1→R2→L3→R4→L1L1 \to R2 \to L3 \to R4 \to L1、L4→R3→L1L4 \to R3 \to L1、R2→L4R2 \to L4 等弧构成一个强连通分量,而 L2L2、R1R1 各自单独成点:

flowchart LR
    subgraph S["同一个强连通分量(两条交错环共用 L1)"]
    L1["左 1"] --> R2["右 2"]
    R2 --> L3["左 3"]
    L3 --> R4["右 4"]
    R4 --> L1
    R2 --> L4["左 4"]
    L4 --> R3["右 3"]
    R3 --> L1
    R4 --> L4
    end
    L2["左 2"] --> R1["右 1"]
    R1 --> L1
    R1 --> L3
    R1 --> L4

逐条对照期望输出 1000 / 0111 / 1000 / 1000(第 1 行):(1,2)(1,2) 是匹配边直接为 0;非匹配边 (1,3)(1,3)、(1,4)(1,4) 的右端点 R3R3、R4R4 与 L1L1 同 SCC,满足条件 (a),也为 0;非匹配边 (1,1)(1,1) 的右端点 R1R1 与 L1L1 不同 SCC,又没有右部自由点,两个条件都不满足,于是为 1。

(实际 MM 的具体取法由 Hopcroft-Karp 决定,不同取法下 DD 的形状会变,但上述两条判据的结论与 MM 的取法无关,这正是该判定成立的原因。)

为什么结论与 MM 的取法无关? 因为判据本身是对"存在某个大小为 nn 的匹配含 ee"这个与 MM 无关的命题给出的充要刻画。可以这样理解:若存在大小为 nn 的匹配 M′M' 含 ee,取 M△M′M \triangle M' 中与 ee 同属一个连通块的那部分——它是一个交错环(若 e∈Me \in M 也成立),或是一条两端在右部自由点上的交错路(若 e∉Me \notin M)。前者给出条件 (a),后者给出条件 (b)。反过来,由 (a) 沿环翻转、由 (b) 沿路翻转,都得到含 ee 的合法匹配。

实现要点:

  1. 最大匹配用 Hopcroft-Karp,O(EV)O(E\sqrt{V})。
  2. 有向图 DD 的弧数恰好等于原图边数(每条边转成一条弧),上界 nm=4.5×105n m = 4.5 \times 10^5,链式前向星开 460005 足够。
  3. DD 的顶点数只有 18001800,Tarjan 用递归也不会爆栈。
  4. 输出时先全部填 1,再把"可用"的边改写成 0;这样非边自动是 1,不需要单独处理。

代码

Python 版:

python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-07 19:03
# update_at: 2026-10-07 19:03

import sys
from collections import deque

INF = 10 ** 9  # 分层 BFS 里"不可达"的层号,比任何真实层号都大
UNMATCHED = -1  # 匹配数组里的"该点未匹配",左、右部共用同一个哨兵

# 类型别名(Python 3.12+ 的 type 语句),相当于 C++ 的 using / typedef
type Adj = list[list[int]]  # 邻接表:顶点自己编号,表中存邻居编号
type Table = list[bytearray]  # 答案表:每行一个字节串,'0' 表示这条边可用


def max_matching(adj: Adj, n: int, m: int) -> tuple[list[int], list[int]]:
    """Hopcroft-Karp:返回 (左部匹配数组, 右部匹配数组) 表示的一个最大匹配。"""
    match_l = [UNMATCHED] * n
    match_r = [UNMATCHED] * m
    dist = [0] * n  # 分层 BFS 中左部点的层号,只对左部点有意义

    def build_layers() -> bool:
        """按未匹配的左部点重新分层,返回本轮是否还存在增广路。"""
        que = deque(u for u in range(n) if match_l[u] == UNMATCHED)
        for u in range(n):
            dist[u] = 0 if match_l[u] == UNMATCHED else INF
        found = False
        while que:
            u = que.popleft()
            for v in adj[u]:
                w = match_r[v]
                if w == UNMATCHED:
                    found = True  # 走到未匹配的右部点,就有增广路
                elif dist[w] == INF:
                    dist[w] = dist[u] + 1  # 沿匹配边继续往下分层
                    que.append(w)
        return found

    def augment(u: int) -> bool:
        """只在分层图上从 u 找一条增广路并翻转沿途匹配。"""
        for v in adj[u]:
            w = match_r[v]
            # v 未匹配(增广路到头),或 v 的匹配对象恰在下一层且它还能继续增广
            can_extend = w == UNMATCHED or (dist[w] == dist[u] + 1 and augment(w))
            if can_extend:
                match_l[u] = v
                match_r[v] = u
                return True
        dist[u] = INF  # 本轮 u 已确认增广失败,后面不再重复搜索
        return False

    while build_layers():
        for u in range(n):
            if match_l[u] == UNMATCHED:
                augment(u)
    return match_l, match_r


def scc_ids(adj: Adj, total: int) -> list[int]:
    """迭代版 Tarjan,返回每个顶点所属的强连通分量编号。"""
    dfn = [0] * total
    low = [0] * total
    comp = [0] * total
    on_stack = [False] * total
    nxt = [0] * total  # 每个顶点下一次要处理的出弧下标
    stack: list[int] = []  # Tarjan 维护的栈
    call: list[int] = []  # 手工模拟递归用的调用栈
    timer = 0
    count = 0
    for root in range(total):
        if dfn[root]:
            continue
        timer += 1
        dfn[root] = low[root] = timer
        stack.append(root)
        on_stack[root] = True
        call.append(root)
        while call:
            u = call[-1]
            if nxt[u] < len(adj[u]):
                v = adj[u][nxt[u]]
                nxt[u] += 1
                if dfn[v] == 0:
                    timer += 1
                    dfn[v] = low[v] = timer
                    stack.append(v)
                    on_stack[v] = True
                    call.append(v)
                elif on_stack[v]:  # 指向栈内已访问点,用 dfn 更新 low
                    low[u] = min(low[u], dfn[v])
            else:
                call.pop()
                if low[u] == dfn[u]:
                    while True:
                        w = stack.pop()
                        on_stack[w] = False
                        comp[w] = count
                        if w == u:
                            break
                    count += 1
                if call:  # 回溯到父亲,把儿子的 low 传上去
                    parent = call[-1]
                    low[parent] = min(low[parent], low[u])
    return comp


def saturated_edges(adj: Adj, match_l: list[int], match_r: list[int], n: int, m: int) -> Table:
    """已知存在大小为 n 的匹配时,逐条边判定它能否入选:可入选填 '0',否则保持 '1'。"""
    ans = [bytearray(b'1' * m) for _ in range(n)]
    # 按匹配 M 定向的交错有向图 D:左部点编号 0..n-1,右部点编号 n..n+m-1
    total = n + m
    dag: Adj = [[] for _ in range(total)]
    for u in range(n):
        for v in adj[u]:
            if match_l[u] == v:
                dag[u].append(n + v)  # 匹配边:左 -> 右
            else:
                dag[n + v].append(u)  # 非匹配边:右 -> 左
    comp = scc_ids(dag, total)
    # 从所有未被 M 匹配的右部点出发,标出 D 上可达的顶点
    reachable = bytearray(total)
    que = deque()
    for v in range(m):
        if match_r[v] == UNMATCHED:
            reachable[n + v] = 1
            que.append(n + v)
    while que:
        x = que.popleft()
        for y in dag[x]:
            if not reachable[y]:
                reachable[y] = 1
                que.append(y)
    for u in range(n):
        row = ans[u]
        for v in adj[u]:
            in_cycle = comp[u] == comp[n + v]  # 条件 (a):这条边落在一条交错环上
            via_free = reachable[n + v] == 1  # 条件 (b):交错路前缀可翻转到这条边
            if match_l[u] == v or in_cycle or via_free:
                row[v] = 48  # 48 == ord('0'),属于某个大小为 n 的匹配
    return ans


def edge_table(adj: Adj, n: int, m: int) -> Table:
    """整题的答案表:无解(左部无法全匹配)时全填 '1',否则交给逐边判定。"""
    match_l, match_r = max_matching(adj, n, m)
    has_full = all(x != UNMATCHED for x in match_l)  # 左部全被匹配才存在大小为 n 的匹配
    if not has_full:
        return [bytearray(b'1' * m) for _ in range(n)]
    return saturated_edges(adj, match_l, match_r, n, m)


def solve() -> None:
    data = iter(sys.stdin.buffer.read().split())
    n = int(next(data))
    m = int(next(data))  # 题面保证 n <= m,算法本身不需要这个条件
    rows = [next(data).decode() for _ in range(n)]
    adj = [[j for j, ch in enumerate(row) if ch == '1'] for row in rows]

    ans = edge_table(adj, n, m)
    sys.stdout.write('\n'.join(row.decode() for row in ans) + '\n')


if __name__ == "__main__":
    solve()

C++ 版(同一算法):

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-07 19:03
 * update_at: 2026-10-07 19:03
 */
// 一本通 1730《二分图》:判定每条边是否属于某个「饱和左部」的匹配(题面保证 n <= m)。
//   1. Hopcroft-Karp 求最大匹配;若匹配数不足 n,则不存在大小为 n 的匹配,全部输出 1。
//   2. 取定一个最大匹配 M,按 M 建交错有向图 D(左部点 1..n,右部点 n+1..n+m):
//        匹配边 u-v 建成弧 u -> v,非匹配边 u-v 建成弧 v -> u。
//   3. 非匹配边 (u,v) 属于某个大小为 n 的匹配,当且仅当
//        (a) u 与 v 在 D 的同一个强连通分量里(该边落在一条交错环上),或
//        (b) v 能从某个「M 未匹配的右部点」沿 D 走到(该边落在一条交错路上,翻转前缀即可)。
//      匹配边本身恒属于。
//   4. 输出取反:属于输出 0,否则(含非边)输出 1。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN = 305;    // 左部点数上限
const int MAXM = 1505;   // 右部点数上限
const int MAXV = MAXN + MAXM;
const int MAXE = 460005; // 有向弧上限:n * m = 300 * 1500 = 450000
const int INF = 0x3f3f3f3f;

int n, m;                 // 左部 n 个点、右部 m 个点(保证 n <= m)
vector<int> g[MAXN];      // g[u] = 左部点 u 的全部右部邻居
int matchL[MAXN];         // matchL[u] = 左部点 u 匹配到的右部点,0 表示未匹配
int matchR[MAXM];         // matchR[v] = 右部点 v 匹配到的左部点,0 表示未匹配
int distL[MAXN];          // 分层 BFS 中左部点 u 的层号,INF 表示本轮不可达

// 链式前向星存交错有向图 D
int head[MAXV];           // head[x] = 顶点 x 的第一条出弧编号
struct Edge {
    int to;               // 弧的终点
    int ne;               // 同起点的下一条弧
};
Edge ed[MAXE];
int edge_cnt;

int dfn[MAXV], low[MAXV]; // Tarjan 的时间戳与回溯值
int stk[MAXV], stk_top;   // Tarjan 的栈
bool in_stk[MAXV];        // 顶点是否还在栈中
int scc_id[MAXV], scc_cnt; // 每个顶点所属的强连通分量编号
int timer;

bool reachable[MAXV];     // 从「M 未匹配的右部点」出发在 D 上可达
char ans[MAXN][MAXM];     // 答案矩阵:1 表示该边不属于任何大小为 n 的匹配
char line[MAXM];          // 读入一行的缓冲

// 往交错有向图 D 里加一条弧 u -> v
void add_edge(int u, int v) {
    edge_cnt++;
    ed[edge_cnt].to = v;
    ed[edge_cnt].ne = head[u];
    head[u] = edge_cnt;
}

// Hopcroft-Karp 的分层:未匹配的左部点为第 0 层,返回本轮是否存在增广路
bool hk_bfs() {
    queue<int> que;
    for (int u = 1; u <= n; u++) {
        if (matchL[u] == 0) {
            distL[u] = 0;
            que.push(u);
        } else {
            distL[u] = INF;
        }
    }
    bool found = false;
    while (!que.empty()) {
        int u = que.front();
        que.pop();
        for (int v : g[u]) {
            int w = matchR[v];
            if (w == 0) {
                found = true;               // 存在一条长度更短或同长的增广路
            } else if (distL[w] == INF) {
                distL[w] = distL[u] + 1;    // 沿匹配边继续分层
                que.push(w);
            }
        }
    }
    return found;
}

// 沿分层图找一条增广路并翻转匹配
bool hk_dfs(int u) {
    for (int v : g[u]) {
        int w = matchR[v];
        if (w == 0 || (distL[w] == distL[u] + 1 && hk_dfs(w))) {
            matchL[u] = v;
            matchR[v] = u;
            return true;
        }
    }
    distL[u] = INF;                         // 本轮 u 已确认失败,避免重复搜索
    return false;
}

// 返回最大匹配的边数
int hopcroft_karp() {
    int cnt = 0;
    while (hk_bfs()) {
        for (int u = 1; u <= n; u++) {
            if (matchL[u] == 0 && hk_dfs(u)) cnt++;
        }
    }
    return cnt;
}

// Tarjan 求强连通分量(D 的顶点数不超过 1800,递归深度安全)
void tarjan(int u) {
    dfn[u] = low[u] = ++timer;
    stk[++stk_top] = u;
    in_stk[u] = true;
    for (int e = head[u]; e; e = ed[e].ne) {
        int v = ed[e].to;
        if (dfn[v] == 0) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (in_stk[v]) {
            low[u] = min(low[u], dfn[v]);
        }
    }
    if (low[u] == dfn[u]) {
        scc_cnt++;
        int w;
        do {
            w = stk[stk_top--];
            in_stk[w] = false;
            scc_id[w] = scc_cnt;
        } while (w != u);
    }
}

// 从所有「M 未匹配的右部点」出发做 BFS,标出 D 上能到达的顶点
void bfs_from_free_right() {
    queue<int> que;
    for (int v = 1; v <= m; v++) {
        if (matchR[v] == 0) {
            reachable[n + v] = true;
            que.push(n + v);
        }
    }
    while (!que.empty()) {
        int x = que.front();
        que.pop();
        for (int e = head[x]; e; e = ed[e].ne) {
            int y = ed[e].to;
            if (!reachable[y]) {
                reachable[y] = true;
                que.push(y);
            }
        }
    }
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%s", line + 1);
        for (int j = 1; j <= m; j++) {
            if (line[j] == '1') g[i].push_back(j);
        }
    }
    int matched = hopcroft_karp();
    // 默认全部输出 1:非边,以及不属于任何大小为 n 的匹配的边
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) ans[i][j] = '1';
        ans[i][m + 1] = '\0';
    }
    if (matched < n) {
        for (int i = 1; i <= n; i++) puts(ans[i] + 1);
        return 0;
    }
    // 按匹配 M 建交错有向图 D
    for (int u = 1; u <= n; u++) {
        for (int v : g[u]) {
            if (matchL[u] == v) add_edge(u, n + v); // 匹配边:左 -> 右
            else add_edge(n + v, u);                // 非匹配边:右 -> 左
        }
    }
    for (int x = 1; x <= n + m; x++) {
        if (dfn[x] == 0) tarjan(x);
    }
    bfs_from_free_right();
    for (int u = 1; u <= n; u++) {
        for (int v : g[u]) {
            if (matchL[u] == v) ans[u][v] = '0';                 // 匹配边恒属于
            else if (scc_id[u] == scc_id[n + v]) ans[u][v] = '0'; // 条件 (a):交错环
            else if (reachable[n + v]) ans[u][v] = '0';           // 条件 (b):交错路
        }
    }
    for (int i = 1; i <= n; i++) puts(ans[i] + 1);
    return 0;
}

复杂度

设 EE 为边数(E⩽nmE \leqslant nm)。Hopcroft-Karp 时间 O(En)O(E\sqrt{n});建 DD 与 Tarjan 求 SCC 时间 O(n+m+E)O(n + m + E);从自由点出发的 BFS 时间 O(n+m+E)O(n + m + E);最后枚举每条边打答案 O(E)O(E)。总时间 O(En)O(E\sqrt{n}),空间 O(n+m+E)O(n + m + E)。顶格数据 n=300n = 300、m=1500m = 1500、E=4.5×105E = 4.5\times10^5 时,C++ 实测远低于 1s;Python 版为同一算法,最坏点可能接近或超过 1s 限时,属该 skill 允许的 Python TLE 范围,未做算法降级。

总结

本题的模型是"每条边是否属于某个最大匹配",经典结论是两条判据的并集:同强连通分量(交错环)或右端点从自由右部点可达(交错路)。把这两条落成"按匹配边定向 + Tarjan + 一次 BFS",整道题就是 Hopcroft-Karp 加两个线性图论模板的拼接。

三个容易踩的坑:一是 n⩽mn \leqslant m 使问题从"最大匹配"退化为"左部完美匹配",自由点只可能出现在右部,条件 (b) 的源集合只能是 MM 未匹配的右部点;二是无解(最大匹配 <n< n)时必须整体输出全 1,不能继续走后面的判定;三是输出取反——题面要求"不存在这样的匹配才输出 1",写代码时用"先全填 1 再改 0"最不容易错。

关于数据:本题的 data/ 由随题目附带的 data.py 生成(10 个点,含题面 3 个样例与若干随机/顶格点),题面文字也属于网络重建,因此数据并非官方原始测试数据,只是按题面约束构造的自造数据。本仓库的 std.cpp 与本解法思路一致(同样的 Hopcroft-Karp + SCC + 自由点可达),已在全部 10 个点上与 main.cpp 的实跑结果比对一致。