graph - Maximum Bipartite Matching & Vertex Cover

/**************************************************************
    Maximum Matching in Bipartite Graph (Kuhn's Algorithm)
    Complexity : O(VE)
    Input:
    * n = # nodes in Left Part
    * m = # nodes in Right Part;
    * G = Adjacency List Repr. of Graph
    Output:
    * Maximum Matching By maxMatching() function
    * Vertex cover
    * Matched egdes link[]

    Index : 1-based
    Important :
    * Maximum Matching = Minimum Vertex Cover = totalNode - Maximum Independent Set
    * Minimum Edge Cover = Maximum Matching + # of nodes which are not matched
***************************************************************/


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

const int N = 1001;

int n,m;
vector<int>G[N];
int link[N],S[N],T[N], rig[N];

bool dfs(int u)
{
    S[u] = 1;
    for(int i= 0;i < G[u].size(); i ++) {
        int v = G[u][i];
        if(T[v]) continue;
        T[v] = 1;
        if(link[v] == -1 || dfs(link[v])) {
            link[v] = u;
            rig[u] = v;
            return 1;
        }
    }
    return 0;
}

int maxMatching()
{
    int ret = 0;
    memset(link, - 1 , sizeof link);
    memset(rig, -1, sizeof rig );
    for(int i = 1; i <= n ; i ++) {
        memset(S,0,sizeof S);
        memset(T,0,sizeof T);
        if(dfs(i)) ret ++;
    }
    return ret;
}

pair<vector<int>,vector<int> > VerTex_Cover()
{
    vector<int> L,R;
    memset(S,0,sizeof S);
    memset(T,0,sizeof T);

    for(int i = 1;i <= n; i ++) {
        if(rig[i]== -1) dfs(i);
    }

    for(int i = 1; i <= n; i ++) if(!S[i]) L.push_back(i);
    for(int i = 1; i <= m; i ++) if(T[i]) R.push_back(i);
    return make_pair(L,R);
}
/*
    Input Graph :
    5 5 7
    1 2
    3 1
    4 2
    3 5
    2 4
    2 5
    5 1
*/

int main()
{
    //freopen("/home/matrixcode/Documents/code/in.txt","r",stdin);
    int edge,a,b;
    scanf("%d %d %d",&n,&m,&edge);
    for(int i = 0; i < edge; i ++) {
        scanf("%d %d",&a,&b);
        G[a].push_back(b);
    }
    /*
    Expected:
    Maximum Bipartite Matching = 4
    Printing Vertex Cover
    Left Side: 2 3 5
    Right Side: 2
    */
    int match = maxMatching();
    printf("Maximum Bipartite Matching = %d\n",match );
    printf("Printing Vertex Cover\n");
    pair<vector<int>,vector<int> > vc = VerTex_Cover();
    printf("Left Side:");
    for(int i = 0; i < vc.first.size() ; i ++) printf(" %d", vc.first[i]); puts("");
    printf("Right Side:");
    for(int i = 0; i < vc.second.size(); i++ ) printf(" %d", vc.second[i]); puts("");

}