Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 贴个c++代码

Posted by a280920481 at 2018-12-05 21:29:55 on Problem 3041 and last updated at 2018-12-05 22:33:50
```#include <iostream>
using namespace std;

int G[1005][505];//邻接表
int deg[1005];//每个节点的度
int match[1005];//与节点配对的节点
bool used[505];//记录节点是否已被搜索过

bool dfs(int v);//利用二分图的性质优化dfs

int main()
{
int N, K, R, C, ans = 0;

cin >> N >> K;

for (int i = 0; i < K; i++)
{
cin >> R >> C;

G[R][deg[R]++] = N + C;
G[N + C][deg[N + C]++] = R;
}

for (int i = 1; i <= N; i++)
{
for (int i = 1; i <= N; i++)
{
used[i] = false;
}
if (dfs(i))
{
ans++;
}
}

cout << ans << '\n';

return 0;
}

bool dfs(int v)
{
int u, w;//用于临时记录

used[v] = true;

for (int i = 0; i < deg[v]; i++)
{
u = G[v][i];
w = match[u];

if (!w)
{
match[v] = u;
match[u] = v;
return true;
}
else if (!used[w])
{
if (dfs(w))
{
match[v] = u;
match[u] = v;
return true;
}
}
}
return false;
}
```

Followed by: