0

Реализую алгоритм Куна (нахождения наибольшего паросочетания в двудольном графе) в рамках одного из олимпиадных заданий по программированию, так для себя, для подготовки.

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.

Подскажите, как можно дополнить алгоритм, чтобы не было переполнения. Спасибо!

2 ответа 2

0

Так как алгоритм рекурсивный, то ему не хватает размера стека. Способов два - либо уменьшить его использование (к примеру, сократив количество аргументов у метода), либо увеличив размер стека - добавив в командную строку, что-то вида -Xss16M - это даст 16Мб стека.

0

Убрать рекурсию в findPath

2
  • @smackmychi, Постарайтесь писать более развернутые ответы. Поясните, на чем основано ваше утверждение.@smackmychi, Постарайтесь писать более развернутые ответы. Поясните, на чем основано ваше утверждение. 17 сен 2014 в 3:46
  • @smackmychi, Постарайтесь писать более развернутые вопросы. Поясните, в чем вы видите проблему, как ее воспроизвести и т. д. Если так дальше продолжать, боюсь, повторим ошибку ТСа
    – smackmychi
    17 сен 2014 в 8:13

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.