-
Notifications
You must be signed in to change notification settings - Fork 0
/
11375.cpp
61 lines (48 loc) · 959 Bytes
/
11375.cpp
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
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <vector>
#include <memory.h>
using namespace std;
int N, M;
const int MAX_V = 1001;
bool adj[MAX_V][MAX_V];
vector<int> aMatch, bMatch;
vector<bool> visited;
bool dfs(int a) {
if (visited[a]) return false;
visited[a] = true;
for (int b = 1; b <= M; b++) {
if (adj[a][b]) {
if (bMatch[b] == -1 || dfs(bMatch[b])) {
aMatch[a] = b;
bMatch[b] = a;
return true;
}
}
}
return false;
}
int bipartiteMatch() {
int total = 0;
aMatch = vector<int>(N + 1, -1);
bMatch = vector<int>(M + 1, -1);
for (int start = 1; start <= N; start++) {
visited = vector<bool>(N + 1, false);
if (dfs(start))
total++;
}
return total;
}
int main(void) {
int num, t;
scanf("%d%d", &N, &M);
for (int i = 0; i < N; i++) {
scanf("%d", &num);
for (int j = 0; j < num; j++) {
scanf("%d", &t);
adj[i+1][t] = true;
}
}
printf("%d\n", bipartiteMatch());
return 0;
}