Cuplaj maxim in graf bipartit

#include <bits/stdc++.h>

using namespace std;

ifstream fin("cuplaj.in");
ofstream fout("cuplaj.out");

/*
https://www.youtube.com/watch?v=GhjwOiJ4SqU

In order to solve the problem we first need to build a flow network.
Just as we did in the multiple-source multiple-sink problem we will add two “dummy” vertices:
a super-source and a super-sink, and we will draw an edge from the super-source to each of
the vertices in set A(employees in the example above) and from each vertex in set B to the
super-sink. In the end, each unit of flow will be equivalent to a match between an employee
and a job, so each edge will be assigned a capacity of 1. If we would have assigned a
capacity larger than 1 to an edge from the super-source, we could have assigned more than
one job to an employee. Likewise, if we would have assigned a capacity larger than 1 to an
edge going to the super-sink, we could have assigned the same job to more than one employee.
The maximum flow in this network will give us the cardinality of the maximum matching.
It is easy to find out whether a vertex in set B is matched with a vertex x in set A as well.
We look at each edge connecting x to a vertex in set B, and if the flow is positive along one
of them, there exists a match. As for the running time, the number of augmenting paths is
limited by min(|A|,|B|), where by |X| is denoted the cardinality of set X, making the running
time O(N * M), where N is the number of vertices, and M the number of edges in the graph.

An implementation point of view is in place. We could implement the maximum
bipartite matching just like in the pseudocode given earlier. Usually though, we might want
to consider the particularities of the problem before getting to the implementation part,
as they can save time or space. In this case, we could drop the 2-dimensional array that
stored the residual network and replace it with two one-dimensional arrays: one of them
stores the match in set B(or a sentinel value if it doesn’t exist) for each element of set A,
while the other is the other way around. Also, notice that each augmenting path has
capacity 1, as it contributes with just a unit of flow. Each element of set A can be the
first(well, the second, after the super-source) in an augmenting path at most once, so we
can just iterate through each of them and try to find a match in set B. If an augmenting path
exists, we follow it. This might lead to de-matching other elements along the way,
but because we are following an augmenting path, no element will eventually remain unmatched
in the process.
*/

const int NMAX = 1e4 + 4;
vector<int> G[NMAX];
int l[NMAX], r[NMAX];
bool viz[NMAX];

bool dfs(const int &u) {
    if(viz[u])
        return false;
    viz[u] = true;
    for(const int &v : G[u])
        if(!r[v]) {
            l[u] = v;
            r[v] = u;
            return true;
        }
    for(const int &v : G[u])
        if(dfs(r[v])) {
            l[u] = v;
            r[v] = u;
            return true;
        }
    return false;
}

int main() {
    int N, M, E;
    fin >> N >> M >> E;
    while(E--) {
        int u, v;
        fin >> u >> v;
        G[u].emplace_back(v);
    }
    for(bool change = true; change; ) {
        change = false;
        memset(viz, false, sizeof(viz));
        for(int node = 1; node <= N; ++node)
            if(!l[node])
                change |= dfs(node);
    }
    int cuplaj = 0;
    for(int i = 1; i <= N; ++i)
        cuplaj += (l[i] > 0);
    fout << cuplaj << '\n';
    for(int i = 1; i <= N; ++i)
        if(l[i] > 0)
            fout << i << ' ' << l[i] << '\n';
}