HackerEarth Earthland problem solution

In this HackerEarth Earthland problem solution There is a mysterious castle in Earthland. In this castle there are 'n' rooms and each room contains "saviour soul" which need to be freed to fight the evil and save earthland. Once the soul is freed it leads to destruction of the room, additionally there is a pathway where you and your friends are standing which is connected to each of the rooms. The castle is so mysterious that if room1 is connected to room2 means you can only go from room1 to room2 and not vice versa. The mystery doesn't end here, starting from a given room, say room(u) it is impossible to reach back to room(u) following any of the paths. Now you need to free all the saviours to save earthland and sacrifice yourself and friends for it. So determine the minimum of your friends who should accompany you for this holy task.

HackerEarth Earthland problem solution.

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
int L[1005],R[1005],vs[1005],n,m;
vector<int>v[1005];
bool df(int i)
{
    vs[i]=1;
    for(int k=0;k<v[i].size();k++)
    {
        int j=v[i][k];
        if(R[j]==-1)
        {
            R[j]=i;
            L[i]=j;
            return true;
        }
        if(vs[R[j]]==0 && df(R[j]))
        {
            R[j]=i;
            L[i]=j;
            return true;
        }
    }
    return false;
}
void kuhn()
{
    int ans=0,fl=0;
    memset(L,-1,sizeof(L));
    memset(R,-1,sizeof(R));
    do
    {
        fl=0;
        memset(vs,0,sizeof(vs));
        for(int i=1;i<=n;i++)
        {
            if(L[i]==-1)
            {
                bool pp=df(i);
                if(pp==true) ans++,fl=1;
            }
        }
    }while(fl!=0);
    cout<<n-ans-1<<"\n";
}
int main()
{
    //freopen("input.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int tt;
    cin>>tt;
    while(tt--)
    {
        for(int i=0;i<1005;i++) v[i].clear();
        cin>>n>>m;
        while(m--)
        {
            int x,y;
            cin>>x>>y;
            v[x].push_back(y);
        }
        kuhn();
    }
}

Second solution

import java.util.*;
import java.math.*;
import java.io.*;

class Earthland
{
    static List<Integer> graph[], revGraph[];
    static LinkedList<Integer> list;
    static boolean visited[];
    static int assignedTo[];
    static boolean g[][];
    public static void main(String args[])throws Exception
    {
        Scanner in=new Scanner(System.in);
        PrintWriter out=new PrintWriter(System.out);
        int t = in.nextInt();
        while(t-- > 0) {
            int n = in.nextInt(), m = in.nextInt(), i, j, u, v;
            graph = new List[n];
            revGraph = new List[n];
            g = new boolean[n][n];
            for(i=0;i<n;i++) {
                graph[i] = new ArrayList<Integer>();
                revGraph[i] = new ArrayList<Integer>();
            }
            for(i=0;i<m;i++) {
                u = in.nextInt() - 1;
                v = in.nextInt() - 1;
                graph[u].add(v);
                revGraph[v].add(u);
                g[u][v] = true;
            }
            //Topological Sorting is not required.
            //list = new LinkedList<Integer>();
            visited = new boolean[n];
            //for(i=0;i<n;i++) {
            //    if(!visited[i]) {
            //        dfs(i);
            //    }
            //}
            //int a[] = new int[n];
            //for(i=0;i<n;i++) {
            //    a[i] = list.pollFirst();
            //}
            assignedTo = new int[n];
            Arrays.fill(assignedTo, -1);
            int friends = 0;
            for(i=0;i<n;i++) {
                Arrays.fill(visited, false);
                if(!matching(i)) {
                    friends++;
                }
            }
            out.println(friends - 1);
        }
        out.flush();
    }
    public static void dfs(int index) {
        visited[index] = true;
        for(int i=graph[index].size()-1;i>=0;i--) {
            int p = graph[index].get(i);
            if(!visited[p]) {
                dfs(p);
            }
        }
        list.addFirst(index);
    }
    public static boolean matching(int index) {
        int i, p;
        for(i=revGraph[index].size()-1;i>=0;i--) {
            p = revGraph[index].get(i);
            if(!visited[p]) {
                visited[p] = true;
                if(assignedTo[p] < 0 || matching(assignedTo[p])) {
                    assignedTo[p] = index;
                    return true;
                }
            }
        }
        return false;
    }
}