I was working on some excercises from a website to improve my coding and I’m having a bit of trouble with finding an error in the following code.

Input are the edges of a bipartite graph, that is, every line of input contains two distinct integers separated by space. These represent some nodes in the two parts of the graph that are connected by an edge.

Output should be number of edges in the maximum matching.

Example input 1:

1 2 

Example output 1:

1 

Example input 2:

2 3 2 4 2 5 2 6 1 3 1 4 1 5 0 5 0 6 10 11 12 13 14 15 

Example output 2:

6 

I believe I have more or less solved the problem using a modified network flow approach. However, when submitting the code there is a timelimit error from the feeback system; I assume it is caused by an infinite loop somewhere. I have been testing the program for two days and haven’t found the bug, perhaps somebody here can tell me where I made a mistake? Feel free to comment on coding style etc. as well, since I’m still learning.

Performance is also evaluated by the site, so if you see some ways to make the code faster, please tell me too 🙂

Thanks in advance.

public class BipartiteMatching {  private static HashMap<Integer, ArrayList<Integer>> partA; private static HashSet<Integer> partB; //M holds matched pairs private static HashMap<Integer, Integer> M; //A holds edges for augmenting path method private static HashMap<Integer, ArrayList<Integer>> A; //P holds augmenting path private static LinkedList<Integer> P; //holds visited nodes for dfs private static HashSet<Integer> visited;  public static void main (String[] args) {      partA = new HashMap<>();     partB = new HashSet<>();     int nodeB, nodeA;      //parse input     Scanner stdin = new Scanner(System.in);      while (stdin.hasNext()) {         nodeA = stdin.nextInt();         nodeB = stdin.nextInt();          if (!partA.containsKey(nodeA)) {             partA.put(nodeA, new ArrayList<Integer>());         }         partA.get(nodeA).add(nodeB);          if (!partB.contains(nodeB)) {             partB.add(nodeB);         }     }     stdin.close();      M = new HashMap<>();     visited = new HashSet<>();     int length = 0, i = 0, k = 0;      //add augmenting paths to matching     while (findAugmentingPath()) {         P.removeLast();          for (Integer n : P) {             if (i%2 != 0) {                 if (M.containsKey(k)) {                     M.remove(M.get(k));                     M.remove(k);                 }                 if (M.containsKey(n)) {                     M.remove(M.get(n));                     M.remove(n);                 }                 M.put(n, k);                 M.put(k, n);             } else {                 k = n;             }             i++;         }         length = M.size()/2;     }      System.out.println(length); }  private static boolean findAugmentingPath () {     A = new HashMap<>();     //create set A - network flow     //-1 is source, -2 is sink     A.put(-1, new ArrayList<>());     for (Integer x : partA.keySet()) {         for (Integer y : partA.get(x)) {             if (M.get(x) == y) {                 if(!A.containsKey(y)) {                     A.put(y, new ArrayList<>());                 }                 A.get(y).add(x);             } else {                 if(!A.containsKey(x)) {                     A.put(x, new ArrayList<>());                 }                 A.get(x).add(y);             }         }         if (!M.containsKey(x)) {             A.get(-1).add(x);         }     }     for (Integer y : partB) {         if (!M.containsKey(y)) {             if(!A.containsKey(y)) {                 A.put(y, new ArrayList<>());             }             A.get(y).add(-2);         }     }      visited = new HashSet<>();     P = new LinkedList<>();     return dfs(-1); }  //depth first search to -2 (sink) //store path in P private static boolean dfs(int current) {     if (A.containsKey(current)) {         visited.add(current);         for (Integer next : A.get(current)) {             if (next == -2) {                 P.add(current);                 return true;             } else {                 if(!visited.contains(next) && dfs(next)) {                     P.add(current);                     return true;                 }             }         }         visited.remove(current);     }     return false; } 

}