Kuhn's Matching

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2e5 + 5;
vector<int> adj[MAXN];
int match_r[MAXN], vis[MAXN];
int timer;

bool dfs(int u) {
    if (vis[u] == timer) return false;
    vis[u] = timer;
    for (int v : adj[u])
        if (match_r[v] == -1 || dfs(match_r[v]))
            return match_r[v] = u, true;
    return false;
}

int maxMatching(int n) {
    memset(match_r, -1, sizeof match_r);
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        timer++;
        ans += dfs(i);
    }
    return ans;
}