Java - превышен лимит времени для алгоритма рекурсивного Тарьяна - PullRequest
Новая
       46

Java - превышен лимит времени для алгоритма рекурсивного Тарьяна

1 голос
/ 08 ноября 2019

Я использую Алгоритм Тарьяна, чтобы найти критические связи в неориентированном графе. Однако, когда вход имеет 100000 вершин, он иногда генерирует TLE. Я искал вокруг и не мог выяснить, почему.

Я пытался реализовать итеративную версию алгоритма Тарьяна, но не смог понять это. Есть ли дальнейшее улучшение по сравнению с кодом?

Testcase Ссылка: https://leetcode.com/submissions/detail/276043932/testcase/

import java.util.*;

class SevenSixThree {


    // the order of visiting vertices
    private int[] ord;

    // the lowest index of the vertex that this vertex can reach
    private int[] low;

    // keep track of the current order;
    private int count;

    // result
    private List<List<Integer>> result;

    // graph
    private Map<Integer, List<Integer>> graph;

    private boolean[] visited;

    public static void main(String[] args) {
        SevenSixThree s = new SevenSixThree();
        List<List<Integer>> list = new ArrayList<>();
        List<Integer> l1 = new ArrayList<>();
        l1.add(0);
        l1.add(1);
        list.add(new ArrayList<>(l1));

        List<Integer> l2 = new ArrayList<>();
        l2.add(0);
        l2.add(2);
        list.add(new ArrayList<>(l2));

        List<Integer> l3 = new ArrayList<>();
        l3.add(1);
        l3.add(2);
        list.add(new ArrayList<>(l3));

        List<Integer> l4 = new ArrayList<>();
        l4.add(1);
        l4.add(3);
        list.add(new ArrayList<>(l4));

        List<List<Integer>> res = s.criticalConnections(4, list);
        System.out.print(res.toArray().toString());
    }


    public  List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {
        // find bridge of a graph.

        // first, build the graph with map
        HashMap<Integer, List<Integer>> graph = new HashMap<>();
        for (int i = 0; i < n; i++) {
            graph.put(i, new ArrayList<>());
        }


        for (List<Integer> connection : connections) {
            int v = connection.get(0);
            int w = connection.get(1);

            graph.get(v).add(w);
            graph.get(w).add(v);
        }

        ord = new int[n];
        low = new int[n];
        visited = new boolean[n];
        Arrays.fill(visited, false);
        result = new ArrayList<>();

        dfs(0, -1, graph);


        return result;
    }

    private void dfs(int v, int parent, HashMap<Integer, List<Integer>> graph) {
         // visit this vertex
         visited[v] = true;
         ord[v] = count++;
         low[v] = ord[v];

         List<Integer> adjs = graph.get(v);
         for (int w : adjs) {
             if (!visited[w]) {
                 dfs(w, v, graph);
                 low[v] = Math.min(low[w], low[v]);
                 if (low[w] > ord[v]) {
                     List<Integer> bridge = new ArrayList<>();
                     bridge.add(v);
                     bridge.add(w);
                     result.add(bridge);
                 }
             } else {
                 if (w != parent) {
                     low[v] = Math.min(low[v], low[w]);
                 }
             }
         }
     }
...