二分图的初遇Codeforces Round 884 (Div. 1 + Div. 2) E

**二分图的初遇**

在 Codeforces 的第884 轮比赛（Div.1 + Div.2）中，E 题目引起了广泛关注。这个问题涉及到二分图的概念，这是一个非常重要且有趣的话题。

**什么是二分图？**

二分图是一种特殊类型的图，它可以被划分为两个完全相互独立的子集，每个子集中的所有顶点都与另一个子集中的任何顶点没有边。换句话说，二分图是一个图，其中每个顶点要么属于第一个子集中，要么属于第二个子集中，但不可能同时属于这两个子集中。

**E 题目的描述**

在 E 题目中，我们被要求找到一个二分图的最大匹配。如果我们将图中的顶点视为男孩和女孩，那么这个问题就变成了寻找一个男孩-女孩配对方案，使得每个男孩都与一个女孩配对，每个女孩也都与一个男孩配对。

**解决方法**

为了解决这个问题，我们可以使用以下算法：

1. **顶点排序**:首先，我们需要将图中的所有顶点按照一定的顺序排列。这可以通过使用拓扑排序或其他方法来实现。
2. **匹配建立**:接下来，我们需要建立一个匹配。我们可以从第一个顶点开始，尝试与它相连的顶点中找到一个没有被匹配的顶点。如果找到了这样的顶点，我们就将它们匹配起来，然后移动到下一个顶点。
3. **回溯**:如果我们无法在某个顶点上建立匹配，那么我们需要回溯到之前的顶点，尝试重新建立匹配。

**代码示例**

cpp#include <iostream>
#include <vector>

using namespace std;

const int N =100010;
int n, m;
bool vis[N];
vector<int> G[N];

void dfs(int u) {
 vis[u] = true;
 for (auto v : G[u]) {
 if (!vis[v]) {
 vis[v] = true;
 dfs(v);
 }
 }
}

int main() {
 cin >> n >> m;

 // 建立图 for (int i =0; i < n + m; ++i) {
 int u, v;
 cin >> u >> v;
 G[u].push_back(n + v);
 G[n + v].push_back(u);
 }

 int ans =0;

 // 匹配建立 for (int i =1; i <= n; ++i) {
 if (!vis[i]) {
 vis[i] = true;
 dfs(i);

 // 回溯 for (auto v : G[i]) {
 vis[v] = false;
 }

 ans++;
 }
 }

 cout << ans << endl;

 return0;
}