public class HungarianAlgorithm {
public static boolean find(List<List<Integer>> adjList, int start, boolean[] visited, int[] match) {
if (adjList.size() == 0 || adjList.get(0).size() == 0) {
return false;
}
for (int next : adjList.get(start)) {
if (!visited[next]) {
visited[next] = true;
// next is not matched or we find an augmented path
if (match[next] == -1 || find(adjList, next, visited, match)) {
match[next] = start;
return true;
}
}
}
return false;
}
public static int hungarian(int[][] relations, int n) {
// Construct adjacent list
List<List<Integer>> adjList = new ArrayList<>();
for (int i = 0; i < n; i++) {
adjList.add(new ArrayList<>());
}
for (int[] relation : relations) {
adjList.get(relation[0]).add(relation[1]);
}
boolean[] visited = new boolean[n];
int[] match = new int[n];
Arrays.fill(match, -1);
int res = 0;
for (int i = 0; i < n; i++) {
if (find(adjList, i, visited, match)) {
++res;
}
// We need to clear visited array before we find the match for the next candidate
Arrays.fill(visited, false);
}
System.out.println("Final Matching");
for (int i = 0; i < n; i++) {
System.out.println("Match " + i + " with " + match[i]);
}
return res;
}
public static void main(String[] args) {
int[][] relations = {{0, 0}, {0, 1}, {1, 1}, {1, 2}, {2, 0}, {2, 1}, {3,2}};
int n = 4;
int matches = hungarian(relations, n);
System.out.println("The maximal matching is " + matches);
}
}