- 【範例】TIOJ 1089 . Asteroids
- 用 DFS 找二分圖的最大匹配數目
- g[xi][yj]：1 表示 xi 和 yj 之間可連通，反之為 0。
- a[yj] = xi：表示把 yj 配對給 xi。
- vis[yj]：表示 yj 已經被拜訪過。檢查每個新的 x 前都要先初始化 vis[ ] (Line-27)。
- 枚舉 x
- dfs (x)：枚舉 y，進行匹配。
- (Line-11) 如果找到一個 y (= i) 是未曾與別的 x 配對 (a[i] = 0)，則可以把 x 配對給 i (a[i] = x)。
- (Line-11) 如果 y (= i) 曾經與別的 x 配對 (a[i] != 0)，則試試看能不能改變該 x 的配對方式，dfs (a[i])。成功改配的話，還是可以把 x 配對給 i (a[i] = x)。
- 【圖例】
- dfs (x1)：a[y2] = x1, vis[y2] = 1
- dfs (x2)：a[y3] = x2, vis[y3] = 1
- dfs (x3)：a[y1] = x3, vis[y1] = 1
- dfs (x4)：a[y1] != 0 –> dfs (a[y1] = x3) –> (此時 vis[1] = vis[2] = vis[3] = 1) a[y4] = x1, a[y1] = x4
#include <iostream>
#include <cstring>
using namespace std;
int n, k, r, c, g[505][505], a[505], vis[505], ans;
bool dfs(int x){
for (int i = 1; i <= n; i++){
if (g[x][i] == 1 && vis[i]==0){
vis[i] = 1;
if (a[i]==0 || dfs(a[i])){
a[i] = x;
return 1;
}
}
}
return 0;
}
int main() {
cin >> n >> k;
for (int i = 0; i < k; i++){
cin >> r >> c;
g[r][c] = 1;
}
for (int i = 1; i <= n; i++){
memset(vis, 0, sizeof(vis));
if (dfs(i)) ans++;
}
cout << ans << "\n";
}
Post Views (since April 2021) : 907