Реализую алгоритм Куна (нахождения наибольшего паросочетания в двудольном графе) в рамках одного из олимпиадных заданий по программированию, так для себя, для подготовки.
g[i] - это массив, в котором i - номер вершины одной части двудольного графа, g[i] хранит массив номеров вершин другой части этого двудольного графа, с которыми i-я вершина связана ребром.
vis[] - массив, в котором отмечаю, была ли уже посещена вершина при поиске увеличивающейся цепи.
matching[] - массив, изначально состоящий из "-1", но при поиске увеличивающейся цепи постепенно заполняется, хранит номер вершины, с которой вершина v была связана в этой цепи.
static boolean findPath(List<Integer>[] g, int u1, int[] matching, boolean[] vis) {
vis[u1] = true;
for (int v : g[u1]) {
int u2 = matching[v];
if (u2 == -1 || !vis[u2] && findPath(g, u2, matching, vis)) {
matching[v] = u1;
return true;
}
}
return false;
}
public static int maxMatching(List<Integer>[] g) {
int n = g.length;
int[] matching = new int[n];
Arrays.fill(matching, -1);
int matches = 0;
for (int u = 0; u < n; u++) {
if (findPath(g, u, matching, new boolean[n]))
matches++;
}
return matches;
}
Собственно, выскакивает ошибка переполнения стека:
Exception in thread "main" java.lang.StackOverflowError
at java.util.ArrayList.iterator(ArrayList.java:814)
Выскакивает при N=18300 (0<i<N)
- количество элементов массива g[], а каждый элемент g[i] хранит по 4 значения. А по идее максимальное значение N (по задаче) должно быть 45000.
Подскажите, как можно дополнить алгоритм, чтобы не было переполнения. Спасибо!