[Java] Build subtrees recursively O(n^2 * number of subtrees)
I thought I would share a different idea.\nI generate the list of all subtrees recursively, by "removing a leaf" every time. To find the order of leaves, I used
I thought I would share a different idea.\nI generate the list of all subtrees recursively, by "removing a leaf" every time. To find the order of leaves, I used dfs preorder.\nTo find the distances between all pairs of vertices I used BFS.\nOther than that, the code should be pretty straitforward (but pretty long, I know).\n\nThe time complexity should be O(n^2 * number of subtrees) : building the list of subtrees takes time O(n * number of subtrees), and checking the distances for each subtree takes O(n^2 * number of subtrees). Unfortunately, the number of trees can be as large as ~2^(n - 1) for the star, so the worst case complexity is the same as checking all subsets.\n\n```\n    public int[] countSubgraphsForEachDiameter(int n, int[][] edges) {\n        \n        ArrayList<Integer>[] graph = (ArrayList<Integer>[]) new ArrayList[n];\n        for (int i = 0; i < n; i++) graph[i] = new ArrayList<>();\n        for (int[] edge : edges){\n            graph[edge[0] - 1].add(edge[1] - 1);\n            graph[edge[1] - 1].add(edge[0] - 1);\n        }\n        List<Integer> postOrder = new ArrayList<>();\n        getPostorder(graph, 0, new boolean[n], postOrder);\n        \n        int[][] distances = new int[n][n];\n        for (int i = 0; i < n; i++)\n            calculateDistances(graph, i, distances);\n\n        List<List<Integer>> subtrees = buildAllSubtrees(graph, new boolean[n], postOrder, 0);\n        int[] ans = new int[n - 1];\n        for (List<Integer> subTree : subtrees){\n            if (subTree.size() < 2) continue;\n\t\t\t\n\t\t\t// find the maximum distance between two vertices from this subtree\n            int max = -1;\n            for (int i = 0; i < subTree.size(); i++)\n                for (int j = i + 1; j < subTree.size(); j++)\n                    max = Math.max(max, distances[subTree.get(i)][subTree.get(j)]);\n            ans[max - 1]++;\n        }\n\t\t\n        return ans;\n    }\n    \n    // get the postorder of vertices using DFS\n    \n    private void getPostorder(ArrayList<Integer>[] graph, int start, boolean[] visited, List<Integer> postOrder){\n        visited[start] = true;\n        for (int i : graph[start]){\n            if (visited[i]) continue;\n            getPostorder(graph, i, visited, postOrder);\n        }\n        postOrder.add(start);\n    }\n    \n    // find distances between all pairs using BFS\n    \n    private void calculateDistances(ArrayList<Integer>[] graph, int start, int[][] distances){\n        Queue<Integer> queue = new LinkedList<>();\n        queue.add(start);\n        int dist = 0;\n        boolean[] visited = new boolean[distances.length];\n        while (!queue.isEmpty()){\n            int size = queue.size();\n            for (int i = 0; i < size; i++){\n                int vertex = queue.poll();\n                visited[vertex] = true;\n                distances[start][vertex] = dist;\n                for (int neigh : graph[vertex]){\n                    if (!visited[neigh]) queue.add(neigh);\n                }\n            }\n            dist++;\n        }\n    }\n    \n    \n    // build the set of all subtrees by visiting vertices in the postorder\n    // in this way the current vertex will always be the leaf in the subtree up to current\n    \n    private List<List<Integer>> buildAllSubtrees(ArrayList<Integer>[] graph, boolean[] visited, List<Integer> order, int current){\n        if (current == order.size())\n            return new ArrayList<>();\n        \n        int leaf = order.get(current);\n        \n        // find the unique neighbor of the leaf\n        int neighbor = -1;\n        for (int neigh : graph[leaf]){\n            if (!visited[neigh]){\n                neighbor = neigh;\n                break;\n            }\n        }\n                \n        visited[leaf] = true;\n        \n        // find the subtrees if we remove the leaf\n        List<List<Integer>> list = buildAllSubtrees(graph, visited, order, current + 1);\n        \n        // for each subset, if it contains the unique neighbor, add a copy of it with the leaf\n        List<List<Integer>> newAns = new ArrayList<>();\n        for (List<Integer> subTree : list){\n            newAns.add(subTree);\n            if (subTree.contains(neighbor)){\n                List<Integer> newList = new ArrayList(subTree);\n                newList.add(leaf);\n                newAns.add(newList);\n            }\n        }\n        \n        // add the subtree that only contains leaf\n        List<Integer> single = new ArrayList<>();\n        single.add(leaf);\n        newAns.add(single);\n        \n        return newAns;\n    }
['Depth-First Search', 'Breadth-First Search', 'Recursion', 'Java']