[Leetcode] 3372. Maximize the Number of Target Nodes After Connecting Trees I

https://leetcode.com/problems/maximize-the-number-of-target-nodes-after-connecting-trees-i/description/

initial

i thought about dfsing on every node of tree 1 and tree 2. But actually the question asks how many nodes we can reach from node i of first tree with depth = k. So naturally we can precalc

1) all the nodes within depth of k and less in firs tree
2) we have to connect each node of first tree to any node of second tree. Second tree will thus have a depth of k-1 and its minus one cuz first tree's node must be accounted for and takes up depth of 1 to traverse before traversal can reach second tree. The maximum value that node in second tree has with depth=k-1 is the answer that we can add to the final ans.

be careful to rmb to make a visited list for each dfs traversal, not reuse it

sol

class Solution {
    public int[] maxTargetNodes(int[][] edges1, int[][] edges2, int k) {
        List<List<Integer>> graph1 = new ArrayList<>();
        List<List<Integer>> graph2 = new ArrayList<>();
        int n1 = edges1.length+1;
        int n2= edges2.length+1;
        int[] ans = new int[n1];
        for(int i=0;i<n1;i++){
            graph1.add(new ArrayList<>());
        }
        for(int i=0;i<n2;i++){
            graph2.add(new ArrayList<>());
        }

        for(int[] edge:edges1){
            int start = edge[0], end = edge[1];
            graph1.get(start).add(end);
            graph1.get(end).add(start);
        }
        for(int[] edge:edges2){
            int start = edge[0], end = edge[1];
            graph2.get(start).add(end);
            graph2.get(end).add(start);
        }
        int[] count1 = new int[n1];
        int[] count2= new int[n2];
        for(int i =0; i<n1;i++){
            boolean[] visited1 = new boolean[n1];
            dfs(graph1,count1, i,i, 0, k,visited1);
        }
        for(int i =0; i<n2;i++){
            boolean[] visited2 = new boolean[n2];
            dfs(graph2,count2, i,i, 0, k-1,visited2);
        }
        int maxCount2 = 0;
        for (int c : count2) {
            maxCount2 = Math.max(maxCount2, c);
        }
        for(int i =0;i<n1;i++){
            ans[i]= count1[i]+maxCount2;
        }
        return ans;
    }
    public void dfs(List<List<Integer>> graph1, int[] count1, int original, int cur, int depth, int k, boolean[] visited){
        if(depth>k || visited[cur]) return;
        visited[cur]=true;
        count1[original]++;
        for(int neigh:graph1.get(cur)){
            if(!visited[neigh]){
                dfs(graph1,count1,original,neigh,depth+1,k,visited);
            }
        }
    }
}

complexity

so each of the nodes can visit up to depth k, so
n*k where n is number of nodes for time

for space, the double arraylist is the largest space concern and is n+e (or v+e) where n and v again is number of nodes