Khun

 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
vector< vector<int> > g;
vector<int> mt;
vector<bool> used;
const int undef = -1;
int n1, n2;
void init() {
g.assign(n1, vector<int>());
//graph init
mt.assign(n2, undef);
}
bool try_khun(int v) {
if(used[v]) return false;
used[v] = true;
for(int u : g[v]) {
if(mt[u] == undef || try_khun(mt[u])) {
mt[u] = v;
return true;
}
}
return false;
}
void solve() {
init();
for(int i = 0; i < n1; i++) {
used.assign(n1, false);
try_khun(i);
}
}