二部マッチング

class bipartite_matching{
public:
    int nL,nR;
    vector<vector<int>> g;
    vector<int> dist;
    vector<int> matchL,matchR;

    bipartite_matching(int L,int R){
        nL = L;
        nR = R;
        g.resize(nL);
        matchL.assign(nL,-1);
        matchR.assign(nR,-1);
        dist.resize(nL);
    }

    void add_edge(int l,int r){
        // l : 0..nL-1, r : 0..nR-1
        g[l].push_back(r);
    }

    bool bfs(){
        queue<int> q;
        for(int i = 0;i < nL;i++){
            if(matchL[i] == -1){
                dist[i] = 0;
                q.push(i);
            }
            else{
                dist[i] = -1;
            }
        }

        bool reachable = false;

        while(!q.empty()){
            int v = q.front();
            q.pop();
            for(int to : g[v]){
                int u = matchR[to];
                if(u >= 0){
                    if(dist[u] < 0){
                        dist[u] = dist[v] + 1;
                        q.push(u);
                    }
                }
                else{
                    reachable = true;
                }
            }
        }
        return reachable;
    }

    bool dfs(int v){
        for(int to : g[v]){
            int u = matchR[to];
            if(u < 0 || (u >= 0 && dist[u] == dist[v] + 1 && dfs(u))){
                matchL[v] = to;
                matchR[to] = v;
                return true;
            }
        }
        dist[v] = -1;
        return false;
    }

    int max_matching(){
        int res = 0;
        while(bfs()){
            for(int i = 0;i < nL;i++){
                if(matchL[i] == -1){
                    if(dfs(i)){
                        res++;
                    }
                }
            }
        }
        return res;
    }
};