# SPOJ Fast Matching challenge

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
{
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++)
{
int u = Integer.parseInt(strArr[0]);
int v = Integer.parseInt(strArr[1]);
}
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
{
{
if(dist[pairV[v]] == dist[u] + 1)
{
if(dfs(pairV[v],g,pairU,pairV,dist) == true)
{
pairU[u] = v;
pairV[v] = u;
return true;
}
}
}
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;
}
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])
{
{
//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;

• 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. – maaartinus Dec 4 '17 at 15:02