3
\$\begingroup\$

I wrote a solution to the MATCHING challenge on SPOJ:

FJ has N (1 ≤ N ≤ 50,000) cows and M (1 ≤ M ≤ 50,000) bulls. Given a list of P (1 ≤ P ≤ 150,000) potential matches between a cow and a bull, compute the greatest number of pairs that can be matched. Of course, a cow can be matched to at most one bull, and vice versa.

Input

The first line contains three integers, N, M, and P. Each of the next P lines contains two integers A (1 ≤ A ≤ N) and B (1 ≤ B ≤ M), denoting that cow A can be matched with bull B.

Output

Print a single integer that is the maximum number of pairs that can be obtained.

Example Input:

5 4 6  
5 2  
1 2  
4 3  
3 1  
2 2  
4 4

Example Output:

3

I have implemented the hopcroft-karp algorithm in java which is giving me TLE. Maybe I am not implementing the algorithm correctly or maybe if i implement this in different language, is it likely to get passed?

import java.io.*;
import java.util.ArrayDeque;
import java.util.ArrayList;


class Node
{
    public int vertexNum;
    public Node next;
    public Node(int vertexNum)
    {
        this.vertexNum = vertexNum;
        this.next = null;
    }
}

class Graph
{
    int U;
    int V;
    int E;
    int target;
    Node[] u_set = null;
    Node[] v_set = null;

    public Graph(int U,int V,int E)
    {
        this.U = U;
        this.V = V;
        this.E = E;
        //target is the terminating dummy vertex;
        this.target = 0;
        //0 in U set represents the one Unique(extra) node.
        u_set = new Node[U + 1];
        //v_set = new Node[V + 1];
        for(int i = 1 ; i < U + 1 ; i++)
            u_set[i] = new Node(i);

        /*for( int i = 1 ; i < V + 1 ; i++)
            v_set[i] = new Node(i);*/
    }
}


public class Main
{
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] strArr = br.readLine().split(" ");
        int U = Integer.parseInt(strArr[0]);
        int V = Integer.parseInt(strArr[1]);
        int E = Integer.parseInt(strArr[2]);
        Graph g = new Graph(U,V,E);
        for(int i = 1 ; i <= E; i++)
        {
            strArr = br.readLine().split(" ");
            int u = Integer.parseInt(strArr[0]);
            int v = Integer.parseInt(strArr[1]);
            addEdge(g,u,v);
        }
        System.out.println(hopcroft(g));
    }

    public static void addEdge(Graph g,int u,int v)
    {
        Node n = new Node(v);
        Node temp = g.u_set[u].next;
        g.u_set[u].next = n;
        n.next = temp;

        /*n = new Node(u);
        temp = g.v_set[v].next;
        g.v_set[v].next = n;
        n.next = temp;*/
    }

    public static int hopcroft(Graph g)
    {
        int matching = 0;
        int[] pairU = new int[g.U + 1];
        int[] pairV = new int[g.V + 1];
        int[] dist = new int[g.U + 1];
        for(int i = 1 ; i < g.U + 1 ; i++)
            pairU[i] = 0;
        for(int i = 1 ; i < g.V + 1 ; i++)
            pairV[i] = 0;

        while(bfs(g,pairU,pairV,dist))
        {
            for(int i = 1 ; i < g.U + 1 ; i++)
            {
                if(pairU[i] == 0)
                {
                    if(dfs(i,g,pairU,pairV,dist) == true)
                    {
                        //System.out.println("here first");
                        matching++;
                    }
                }
            }
        }
        return matching;
    }

    public static boolean dfs(int u,Graph g,int[] pairU,int[] pairV,int[] dist)
    {
        if(u == 0)
            return true;
        else
        {
            Node adj = g.u_set[u].next;
            while(adj != null)
            {
                int v = adj.vertexNum;
                if(dist[pairV[v]] == dist[u] + 1)
                {
                    if(dfs(pairV[v],g,pairU,pairV,dist) == true)
                    {
                        pairU[u] = v;
                        pairV[v] = u;
                        return true;
                    }
                }
                adj = adj.next;
            }
            dist[u] = Integer.MAX_VALUE;
            return false;
        }
    }

    public static boolean bfs(Graph g,int[] pairU,int[] pairV,int[] dist)
    {
        ArrayDeque<Integer> queue = new ArrayDeque<Integer>();
        for(int i = 1 ; i < g.U + 1 ; i++)
        {
            if(pairU[i] == 0)
            {
                dist[i] = 0;
                queue.addLast(i);
            }
            else
                dist[i] = Integer.MAX_VALUE;
        }
        dist[g.target] = Integer.MAX_VALUE;
        //System.out.println("bfs start");
        while(queue.size() != 0)
        {
            int u = queue.pollFirst();
            //System.out.println("here, u = " + u + ",pair[u] = " + pairU[u]);
            if(dist[u] < dist[g.target])
            {
                Node adj = g.u_set[u].next;
                while(adj != null)
                {
                    int v = adj.vertexNum;
                    //System.out.println("u = " + u + ", v = " + v + ", pair[v] = " + pairV[v] + ", dist[pair[v]] = " + dist[pairV[v]]);
                    //System.out.println("v = " + v + ", pair[v] = " + pairV[v]);
                    if(dist[pairV[v]] == Integer.MAX_VALUE)
                    {
                        //System.out.println("changing the dist of " + pairV[v]);
                        dist[pairV[v]] = dist[u] + 1;
                        queue.addLast(pairV[v]);
                    }
                    adj = adj.next;
                }
            }
        }
        //System.out.println("dist[target] = " + dist[g.target]);
        return dist[g.target] != Integer.MAX_VALUE;
    }
}
\$\endgroup\$
  • \$\begingroup\$ You may want to look at speed of the input parsing: I've already seen code which timed out just because of this. Your InputStreamReader uses the platform encoding, which may be UTF-8 and that may cost too much time (using LATIN-1 is a trivial fix you can try). Get a big problem instance and measure the time taken by the input. \$\endgroup\$ – maaartinus Dec 4 '17 at 15:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.