匈牙利算法

这是一个为你准备的、可以直接发布在博客或教学网页上的匈牙利算法（二分图最大匹配）教程。

我采用了由浅入深的结构，配合生动的比喻，并针对你提供的 C++ 代码进行了逐行解析。

1. 什么是二分图匹配？

想象我们有两组对象，比如 “学生” 和 “座位”。

• 左边集合：一群学生。
• 右边集合：一排座位。
• 连线（边）：如果某个学生愿意坐某个座位，他们之间就有一条线。

二分图（Bipartite Graph） 指的就是这样一个图：所有的点分成两边，线只在两边之间连接，同边的点之间没有连线。

最大匹配（Maximum Matching） 的目标是：在不发生冲突的情况下（一个座位只能坐一人，一人只能坐一个座位），让尽可能多的学生坐下。

2. 核心思想：增广路（The Augmenting Path）

怎么找到最大匹配呢？匈牙利算法的核心就是寻找增广路。

不用死记硬背数学定义，我们用一个**“腾位置”**的策略来理解：

1. 先到先得：学生 A 来了，看到座位 1 空着，直接坐下。
2. 协商调整：
   • 学生 B 来了，他也只想坐座位 1。
   • 这时发生了冲突。学生 B 不会马上走，而是问学生 A：“兄弟，你能不能换个座？”
   • 学生 A 看了看，发现自己其实也愿意坐座位 2，而且座位 2 空着。
   • 于是：学生 A 去坐座位 2，把座位 1 让给学生 B。
   • 结果：大家都坐下了！匹配数 +1。

这种“你挪一挪，我就能进去，从而大家都开心”的路径，在算法里就叫“增广路”。

匈牙利算法的本质：

每个人都尝试找座位。如果看中的座位有人了，就尝试让那个人挪一挪；如果那个人挪了以后占了别人的位子，就让下一个人再挪一挪……直到找到一个空位，或者大家都挪不动为止。

3. 代码实现精讲 (C++ DFS版)

下面我们使用 DFS (深度优先搜索) 来实现这个“协商”过程。这个版本的代码以简洁和易于理解著称，非常适合算法竞赛（如 Codeforces）。

3.1 数据结构定义

我们使用邻接表存图，节省空间。

        
1
2
3
4
5
6

        const int MAXN = 2005; // 最大点数，根据题目调整

vector<int> adj[MAXN]; // 邻接表：adj[u] 存的是【左边】学生 u 愿意坐的所有座位
int match[MAXN];       // match[v] = u：核心数组！记录【右边】座位 v 目前被谁(u)坐了
bool vis[MAXN];        // 标记数组：在一次协商(DFS)中，座位 v 是否被问过了

    

3.2 核心逻辑：DFS 协商函数

这是算法的灵魂。dfs(u) 的含义是：左边的学生 u 能不能找到座位？

        
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) {
    // 遍历学生 u 喜欢的所有座位 v
    for (int v : adj[u]) {
        
        // 如果在这个轮次的协商中，座位 v 已经被问过了，就别问了，防止死循环
        if (vis[v]) continue; 
        vis[v] = true; // 标记：这个座位我问过了

        // 【核心判断】
        // 情况 1: match[v] == 0 
        //      -> 座位 v 没人坐 (单身)，太好了，直接占领！
        // 情况 2: dfs(match[v])
        //      -> 座位 v 有人坐了 (那个人是 match[v])。
        //      -> 关键：让目前坐在这的人 (match[v]) 去找找别的座 (递归调用 dfs)。
        //      -> 如果他能找到别的座，由于他腾出了位置，我也能坐这了！
        
        if (match[v] == 0 || dfs(match[v])) {
            match[v] = u; // 协商成功！座位 v 现在归 u 了
            return true;  // 也就是 u 找到座了
        }
    }
    return false; // 找了一圈，没空位，也没人愿意腾位置，u 失败了
}

    

3.3 主流程：匈牙利算法

就像点名一样，让左边的学生一个个出来找座位。

        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

        int hungarian(int n) { 
    int ans = 0; // 记录最大匹配数
    memset(match, 0, sizeof(match)); // 一开始所有座位都是空的
    
    // 让左边的 n 个学生依次尝试找座位
    for (int i = 1; i <= n; i++) {
        // 【重要】每次新的人(i)出来找座位，都是新的一轮协商。
        // 所以要把“被问过”的标记清空。
        // 比如上次 A 问过座位 1，但这回是 B 来问，B 还可以再问一次座位 1。
        memset(vis, 0, sizeof(vis)); 
        
        if (dfs(i)) { // 如果学生 i 找到了座位 (或者是通过别人腾位置坐下的)
            ans++;    // 匹配总数 +1
        }
    }
    return ans;
}

    

4. 完整模板 (可以直接 Copy)

这是整合好的标准模板，采用了 I/O 优化，适用于大多数算法竞赛题目。

        
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

        #include <iostream>
#include <vector>
#include <cstring> 
#include <algorithm>

using namespace std;

// --- 匈牙利算法模板 Start ---
const int MAXN = 2005; 
vector<int> adj[MAXN]; 
int match[MAXN];       
bool vis[MAXN];        

void add_edge(int u, int v) {
    adj[u].push_back(v);
}

bool dfs(int u) {
    for (int v : adj[u]) {
        if (vis[v]) continue; 
        vis[v] = true;        
        if (match[v] == 0 || dfs(match[v])) {
            match[v] = u; 
            return true;
        }
    }
    return false; 
}

int hungarian(int n) { 
    int ans = 0;
    memset(match, 0, sizeof(match)); 
    for (int i = 1; i <= n; i++) {
        memset(vis, 0, sizeof(vis)); 
        if (dfs(i)) ans++;
    }
    return ans;
}
// --- 匈牙利算法模板 End ---

int main() {
    // 速度优化，刷题必备
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, m, e; // n:左边点数, m:右边点数, e:边数
    if (!(cin >> n >> m >> e)) return 0;

    for (int i = 0; i < e; i++) {
        int u, v;
        cin >> u >> v;
        if(v > m || u > n) continue; 
        add_edge(u, v); // 建立单向边：左 -> 右
    }

    cout << hungarian(n) << endl;
    return 0;
}

    

5. 复杂度与总结

• 时间复杂度：最坏情况下是 $O(V \cdot E)$。
  • 其中 $V$ 是顶点数，$E$ 是边数。
  • 解释：我们有 $V$ 个点要匹配，每个点最坏情况要在 DFS 中把所有 $E$ 条边走一遍。
  • 在实际应用中，效率通常远好于最坏情况，对于 $N=1000 \sim 2000$ 的题目通常能 0.1秒内跑完。
• 适用场景：
  • 二分图最大匹配。
  • 最小点覆盖数（Konig 定理：二分图最小点覆盖 = 最大匹配数）。
  • 最大独立集（最大独立集 = 总点数 - 最大匹配数）。

6. 练手题目

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

希望这份教程能帮你彻底掌握匈牙利算法！如有疑问，欢迎在评论区讨论。

代码模板

这是一份为你精心优化的 DFS 二分图最大匹配模板。

为了达到 “心智负担低” 和 “适用 Codeforces” 的目标，我做了以下关键改进：

1. 数据结构升级：从邻接矩阵 ($O(V^2)$) 改为 邻接表 (std::vector)。这是 CP (Competitive Programming) 的标配，能处理 $N, M \le 2000$ 甚至更大的稀疏图，避免 MLE/TLE。
2. 逻辑简化：不再双向记录 match，只记录 右边点匹配了左边哪个点 (match[v] = u)。这足以完成算法，且减少了状态维护的复杂度。
3. 拟人化注释：用通俗的“协商”逻辑解释代码，让你一眼就能看懂。

🚀 优化后的模板 (C++11/14/17/20)

        
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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84

        #include <iostream>
#include <vector>
#include <cstring> // for memset
#include <algorithm>

using namespace std;

// ------------------- 模板开始 -------------------
const int MAXN = 2005; // 根据题目要求修改，一般二分图匹配 N<=2000 左右
vector<int> adj[MAXN]; // 邻接表存图：adj[u] 存的是左边点 u 能连到的右边点 v
int match[MAXN];       // match[v] = u：表示【右边】的点 v 当前匹配了【左边】的点 u
bool vis[MAXN];        // vis[v]：在这一轮 DFS 中，右边的点 v 是否被询问过

// 添加边：u 是左边集合的点，v 是右边集合的点
void add_edge(int u, int v) {
    adj[u].push_back(v);
}

// DFS 寻找增广路
// 这里的 u 是左边的点
bool dfs(int u) {
    // 遍历 u 所有可能的“暧昧对象” v (右边的点)
    for (int v : adj[u]) {
        if (vis[v]) continue; // 这一轮已经问过 v 了，不要重复问
        vis[v] = true;        // 标记：这一轮我问过 v 了

        // 核心逻辑：
        // 1. match[v] == 0: v 还是单身，直接匹配！
        // 2. dfs(match[v]): v 已经有对象了(是 match[v])，那我们要去尝试
        //    让 v 的现任对象 (match[v]) 去找别人 (递归查找)。
        //    如果 v 的现任能找到下家，那 v 就空出来了，u 就可以和 v 匹配。
        if (match[v] == 0 || dfs(match[v])) {
            match[v] = u; // 协商成功，v 现在属于 u
            return true;
        }
    }
    return false; // 找了一圈没找到
}

// 匈牙利算法主函数
int hungarian(int n) { // n 是左边集合点的数量
    int ans = 0;
    // match 数组初始化为 0，表示右边点都没匹配
    // 注意：如果点编号包含 0，则需要初始化为 -1
    memset(match, 0, sizeof(match)); 
    
    // 依次尝试给左边的每一个点 i 找对象
    for (int i = 1; i <= n; i++) {
        // 每次开始找增广路前，重置右边点的访问状态
        // 也就是新的一轮“协商”开始了
        memset(vis, 0, sizeof(vis)); 
        if (dfs(i)) {
            ans++;
        }
    }
    return ans;
}
// ------------------- 模板结束 -------------------

int main() {
    // 开启 IO 优化，适应 Codeforces 大数据量
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, m, e; // n:左边点数, m:右边点数, e:边数
    // 注意：有些题目 m 可能没用，只看边关系，但模板通用
    if (!(cin >> n >> m >> e)) return 0;

    for (int i = 0; i < e; i++) {
        int u, v;
        cin >> u >> v;
        // ⚠️如果题目给的 v 是 1~M 的绝对编号，且可能与 u 重复
        // 比如 u=1, v=1 是两个不同的点，通常不需要处理，因为我们存的是单向关系。
        // 但如果题目是所有点统一编号 (1~N+M)，则需根据题意调整。
        // 这里假设 u ∈ [1, n], v ∈ [1, m]
        if(v > m || u > n) continue; // 简单的边界保护
        add_edge(u, v);
    }

    cout << hungarian(n) << endl;

    return 0;
}

    

我还想知道一个问题: 为什么 vis[v] = true 在回溯的时候, 不把vis 置为 0 ?

这是一个非常敏锐的观察！🕵️‍♂️

在很多迷宫或路径搜索的题目（比如“寻找所有可行路径”）中，我们确实需要在回溯时把 vis 恢复成 false（即撤销操作）。但在这个匈牙利算法的 dfs 里，不恢复 vis 其实是一个基于逻辑必然性的重要优化。

让我们来拆解一下这个逻辑。

假设在同一次外部循环（即给左边的点 u 找对象）的过程中：

1. 我们顺着某条路找到了右边的点 v。
2. v 已经有对象了，是 match[v]（我们叫他 old_u）。
3. 于是我们尝试递归调用 dfs(old_u)，想让他挪挪位置。
4. 结果 dfs(old_u) 返回了 false。

这说明了什么？这说明在当前的局面下，old_u 这个点无论如何都找不到空余的位置可去，对吧？

那么，如果在这次查找的后续过程中，我们通过另一条路又绕回到了 v，如果我们允许再次访问它，我们就会再次去问 old_u：“你能挪挪吗？”

你觉得这时候，old_u 的回答会变吗？🤔

这正是 不回溯 vis 数组 的核心原因：

1. 避免重复计算（剪枝）：vis[v] = true 就像是在门上挂了一个“此路不通”的牌子。后面如果再有路径走到这儿，看到牌子直接绕道走，省去了大量无意义的递归。
2. 防止死循环：如果图里有环，不标记 vis 的话，递归可能会在环里无限转圈，导致栈溢出。

💡 核心设计理念解析

1. 为什么它是“心智负担低”的？

• 单向思维：你只需要思考“左边的点去选右边的点”。原来的代码双向记录 (match[u]=i, match[i]=u) 容易让人在递归时搞混“我现在到底在左边还是右边”。在这个模板里，dfs 的入参永远是左边的点，match 数组的下标永远是右边的点。
• 标准 1-based Index：大多数图论题（尤其是 Codeforces）题目输入都是从 1 开始。这个模板默认 1 开始，match 初始化为 0 代表空，非常直观。

2. 为什么它“适用 Codeforces”？

• 邻接表 (vector)：
  • 空间：$O(V+E)$。如果不这么做，遇到 $V=2000$ 的题开 int G[2000][2000] 会占用约 16MB 内存，虽然看似不大，但在 $V=10^4$ 的稀疏图中直接炸裂。
  • 时间：遍历邻居是 $O(degree(u))$，而矩阵是 $O(V)$。在稀疏图中，DFS 速度会快非常多。
• IO 优化：ios::sync_with_stdio(false) 是打 CF 的基本素养，防止大量的 cin/cout 导致 TLE。
• 通用性：时间复杂度最坏为 $O(V \cdot E)$。一般 $V \le 1000$ 或 $2000$ 时可以放心使用。如果 $V, E$ 到了 $10^5$ 级别，任何 DFS/BFS 匈牙利都会 TLE，那时你需要 Hopcroft-Karp 算法（或者是网络流 Dinic）。

🖼️ 算法图解

为了更直观地理解“协商与取反”的过程，这里有一个简单的示意：

📝 快速记忆口诀 (DFS 内部逻辑)

遍历备胎 v，如果没问过：

1. v 没主？ -> 直接拿下。
2. v 有主？ -> 让 v 的现任 match[v] 去找别人。
3. 现任找到了？ -> 那 v 归我。

希望这个模板能成为你 CP 兵器库里趁手的一件武器！有什么具体题目需要拿来测试一下吗？

正确性证明

我理解的 匈牙利算法 是一个 不停寻找 增广路的过程:为什么从左部的点每个点按顺序尝试计算一次就出结果了呢？为什么不是循环尝试计算，直到每个点都是匹配点了呢？

这是一个非常深刻的问题，直击算法本质！很多初学者（甚至老手）都只是记住了“循环一次”，却没想通“为什么不需要回头看”。

这个问题的答案可以归结为两个核心逻辑：“已匹配的点不会变回未匹配” 和 “前面失败的点，后面机会更渺茫”。

让我们拆解一下这个过程。

1. 核心定心丸：匹配数只会增加，不会减少

匈牙利算法的那个 dfs(u)，本质上是在做一件事情：寻找以 u 为起点的增广路。

根据伯吉定理（Berge’s Lemma），一个匹配是最大匹配，当且仅当图中不存在增广路。

我们在 for (int i = 1; i <= n; i++) 这个循环里，实际上是在尝试：

“以点 i 为起点，能不能找到一条增广路？”

• 如果找到了：根据增广路的定义（未匹配边-匹配边-未匹配边…-未匹配点），我们将路径上的边取反。结果是：匹配边数 +1。
  • 注意：原本已经在匹配中的点，只是换了对象（换了座位），它们依然是匹配状态。
  • 也就是：只要你上岸了，就不会再把你踢下水。 你可能会被迫换个座位，但你一定有座位。
• 如果没找到：说明从点 i 出发，走遍所有能走的路，都没法增加匹配数。

2. 为什么不用“回头看”那些失败的点？

你疑惑的点在于：

“比如我先处理点 1（失败了），然后处理点 2（成功了，且改变了图的匹配状态）。这时候，点 1 会不会因为点 2 的改变，突然又能匹配了？”

答案是：绝对不会。

这是一个非常反直觉但数学上成立的结论：

如果在一个较“空”的匹配状态下，点 1 都找不到增广路；那么当匹配变得更“拥挤”（匹配数增加）后，点 1 更不可能找到增广路。

通俗解释（挤地铁理论）：

1. 时刻 T1：车厢里只有几个人（当前的匹配）。
   • 轮到 点 1 找座位。
   • 点 1 发现自己想坐的位子都有人了。于是点 1 尝试让这些人挪一挪（DFS 递归）。
   • 结果：所有相关的人都说“我挪不了，我挪了就没地儿坐了”。
   • 结论：点 1 宣告失败。这意味着：所有点 1 能接触到的资源，都被“死死地”占用了。
2. 时刻 T2：轮到 点 2 找座位。
   • 点 2 运气好，通过复杂的交涉（DFS），成功挤进去了（找到了增广路）。
   • 注意：点 2 的加入，意味着车厢里又少了一个空位，或者某个人换到了一个原本空着的位子上。
   • 现在的车厢比 T1 时刻更拥挤了。
3. 回头看：
   • 在 T1 那个相对宽松的环境下，点 1 都没能撬动任何一个人挪窝。
   • 在 T2 这个更拥挤（更多点被匹配、更多空位被填满）的环境下，点 1 更加不可能找到位置。

一句话总结：后面加入的匹配，只会抢占更多的资源（右边的点），绝不会凭空创造出新的“腾挪空间”给前面的失败者。

3. 为什么不是“直到每个点都是匹配点”？

你问：“为什么不是循环尝试计算，直到每个点都是匹配点了呢？”

因为很多二分图是不可能完美匹配的（即不可能所有点都有对象）。

比如：左边 5 个男神，右边 3 个妹子。无论你怎么努力，左边至少有 2 个男神是光棍。

算法的目标是 “最大匹配”（能配多少配多少），而不是 “完美匹配”（必须全配上）。

当我们把 $1$ 到 $N$ 遍历一遍后：

1. 能匹配的点，都已经在匹配集合里了。
2. 不能匹配的点，是因为确实没资源了（数学上叫“不存在增广路”）。
3. 再循环一遍，除了浪费 CPU 电费，结果不会有任何变化。

4. 总结：一种特殊的“贪心”

虽然匈牙利算法看起来像是一个个点按顺序处理（像贪心），但因为 dfs 里的**递归取反（回溯）机制，它拥有了“反悔”**的能力。

• 它不是说“点 A 占了座位 1，点 A 就永远占着 1”。
• 它是说“点 A 占了座位 1，但如果有需要，点 A 可以去坐座位 2，把 1 让出来”。

正因为每个点的 DFS 都包含了“尝试所有可能的腾挪方案”，所以一次遍历（1 到 N）就足够穷尽所有的增广路可能性了。

这个逻辑确实很美妙，不是吗？

一些证明

1. 增广路一定有奇数边

好的，我们先明确一下定义和问题。

1. 基本概念

• 二分图：顶点集 $V$ 可以划分为两个不相交的子集 $X$ 和 $Y$，所有边的两个端点分别属于 $X$ 和 $Y$。
• 匹配：一组没有公共顶点的边。
• 交替路：从一个未匹配点出发，依次经过 非匹配边、匹配边、非匹配边、匹配边…… 的路径，且路径上匹配边和非匹配边交替出现。
• 在二分图匹配的讨论中，交替路通常特指从一个未匹配点出发，到另一个未匹配点结束的 增广路（augmenting path）。

2. 交替路的边数奇偶性

设二分图的两个部分为 $X$ 和 $Y$，交替路 $P$ 的起点为未匹配点 $u$，终点为未匹配点 $v$。

情况分析

(1) 起点和终点在同一个部吗？

• 如果 $u, v$ 都在 $X$ 中： 路径的第一条边是从 $X$ 到 $Y$（因为 $u$ 在 $X$ 且未匹配，它只能走非匹配边到 $Y$）。 路径的最后一条边是从 $Y$ 到 $X$（因为 $v$ 在 $X$ 且未匹配，它必须是从 $Y$ 经过一条非匹配边到达 $X$）。 路径在 $X$ 开始，在 $X$ 结束，中间每一条边都是从 $X$ 到 $Y$ 或从 $Y$ 到 $X$。 从 $X$ 出发，要回到 $X$，必须经过偶数条边吗？ 我们数一下： 从 $X$ 到 $Y$ 是第 1 条边（非匹配）， 从 $Y$ 到 $X$ 是第 2 条边（匹配）， 从 $X$ 到 $Y$ 是第 3 条边（非匹配）， …… 最后一条边是从 $Y$ 到 $X$（非匹配）。 路径形式： $X \to Y \to X \to Y \to \dots \to Y \to X$ 从 $X$ 开始，每次到 $Y$ 要 1 条边，从 $Y$ 回到 $X$ 要 1 条边，这样来回一次是 2 条边。 要回到 $X$，必须经过偶数次跨越吗？ 实际上，从 $X$ 出发，第一次到 $Y$ 是 1 条边，第二次回到 $X$ 是 2 条边，第三次到 $Y$ 是 3 条边，第四次回到 $X$ 是 4 条边…… 所以 从 $X$ 出发，最后回到 $X$，经过的边数是偶数。 但交替路的最后一条边是非匹配边且到达 $X$ 的 $v$，所以如果起点和终点都在 $X$，那么边数是偶数。 然而，在二分图匹配的增广路定义中，起点和终点都是未匹配点，如果它们在同一部，那么路径的边数确实是偶数。 但这样会带来问题：偶数条边的交替路，匹配边和非匹配边数量相等，交换后匹配数不变？ 我们检查： 边数偶数，比如 4 条边： 边 1（非匹配），边 2（匹配），边 3（非匹配），边 4（匹配）？不对，这样最后一个顶点是匹配点，不是未匹配点。 实际上，交替路要求起点终点都未匹配，所以路径的边数必须是奇数。 我们来严格推导。

(2) 更严谨的推导

设交替路 $P = v_0 e_1 v_1 e_2 v_2 \dots e_k v_k$，其中 $v_0$ 未匹配，$v_k$ 未匹配，并且 $e_i$ 与 $e_{i+1}$ 一个匹配一个非匹配交替。

已知：

• 在二分图中，$v_0 \in X$ 或 $v_0 \in Y$。
• 因为边是 $X-Y$ 交错的，所以顶点在 $X, Y$ 之间交替： 如果 $v_0 \in X$，则 $v_1 \in Y$，$v_2 \in X$，$v_3 \in Y$，…… 即下标偶数的顶点都在 $X$，下标奇数的顶点都在 $Y$（或者反过来，取决于起点在 $X$ 还是 $Y$）。

关键： $v_k$ 是未匹配点，且 $v_k$ 与 $v_0$ 在不同部吗？ 如果 $v_0 \in X$，则 $v_k$ 必须在 $Y$ 才能让边数 $k$ 是奇数吗？ 我们看下标奇偶性： 设 $v_0 \in X$，则：

所以：

• 若 $k$ 是偶数，则 $v_k \in X$（与 $v_0$ 同部）。
• 若 $k$ 是奇数，则 $v_k \in Y$（与 $v_0$ 不同部）。

(3) 匹配边数与非匹配边数的关系

在交替路中，匹配边和非匹配边交替。 因为起点终点都未匹配，所以第一条边是非匹配边，最后一条边也是非匹配边。 所以非匹配边比匹配边多 1 条。 设匹配边数为 $m$，非匹配边数为 $m+1$，总边数 $k = 2m+1$，是奇数。

因此，交替路的边数一定是奇数。

(4) 回到“起点终点是否同部”问题

从上面 $k$ 奇数可知，若 $v_0 \in X$，则 $v_k \in Y$； 若 $v_0 \in Y$，则 $v_k \in X$。 所以起点和终点一定在不同部。 这也符合直观：在二分图中，一条路径边数为奇数时，起点和终点在不同部；边数为偶数时，起点终点在同部。 因为交替路边数奇数，所以它们在不同部。

3. 结论

证明： 设交替路 $P$ 从未匹配点 $u$ 到未匹配点 $v$，边依次为 $e_1, e_2, \dots, e_k$，其中 $e_1$ 非匹配（因为 $u$ 未匹配），$e_k$ 非匹配（因为 $v$ 未匹配），且匹配边与非匹配边交替出现。 因此非匹配边数 = 匹配边数 + 1。 设匹配边数为 $m$，则总边数 $k = m + (m+1) = 2m+1$，为奇数。 证毕。

最终答案： 交替路中，起点终点都未匹配，匹配边与非匹配边交替，且第一条和最后一条是非匹配边，因此非匹配边比匹配边多 1，总边数为奇数。