(nice!!!)(LeetCode 每日一题) 3372. 连接两棵树后最大目标节点数目 I (贪心+深度优先搜索dfs)

思路：贪心+深度优先搜索dfs。时间复杂度0(n^2+m2)，细节看注释。

第二棵树 ，其实就是找出从某个点出发，k-1步能得到的最大目标节点个数mx。

C++版本：

class Solution {
public:// 构建邻接表void solve(vector<vector<int>>& edge,vector<vector<int>> &g){for(auto e:edge){int x=e[0],y=e[1];g[x].push_back(y);g[y].push_back(x);}}//参数：u表示当前结点、fa表示当前结点的父节点、d表示当前的距离//返回值：当前节点u还能抵达的目标子节点个数int dfs(int u,int fa,int d,vector<vector<int>> &g,int k){if(d>k) return 0;int ans=1;for(auto x:g[u]){if(x==fa) continue;ans+=dfs(x,u,d+1,g,k);}return ans;}vector<int> maxTargetNodes(vector<vector<int>>& edges1, vector<vector<int>>& edges2, int k) {//转成邻接表，便于后续dfs的遍历int n=edges1.size(),m=edges2.size();vector<vector<int>> g1(n+1),g2(m+1);solve(edges1,g1);solve(edges2,g2);//第二棵树 ，k-1步能得到的最大目标节点个数mx。int mx=0;for(int i=0;i<=m;i++){int t=dfs(i,-1,0,g2,k-1);mx=max(mx,t);}//答案vector<int> v;for(int i=0;i<=n;i++){int t=dfs(i,-1,0,g1,k);v.push_back(t+mx);//cout<<t<<"---"<<mx<<endl;}return v;}
};

JAVA版本：

class Solution {void solve(int[][] edge,List<List<Integer>> g){for(var e:edge){int x=e[0],y=e[1];g.get(x).add(y);g.get(y).add(x);}}int dfs(int u,int fa,int d,List<List<Integer>> g,int k){if(d>k) return 0;int ans=1;for(var x:g.get(u)){if(x==fa) continue;ans+=dfs(x,u,d+1,g,k);}return ans;}public int[] maxTargetNodes(int[][] edges1, int[][] edges2, int k) {int n=edges1.length,m=edges2.length;List<List<Integer>> g1=new ArrayList<>();List<List<Integer>> g2=new ArrayList<>();for(int i=0;i<=n;i++){g1.add(new ArrayList<Integer>());}for(int i=0;i<=m;i++){g2.add(new ArrayList<Integer>());}solve(edges1,g1);solve(edges2,g2);int mx=0;for(int i=0;i<=m;i++){int t=dfs(i,-1,0,g2,k-1);mx=Math.max(mx,t);}int[] v=new int[n+1];for(int i=0;i<=n;i++){int t=dfs(i,-1,0,g1,k);v[i]=t+mx;//cout<<t<<"---"<<mx<<endl;}return v;}
}

Go版本：

func maxTargetNodes(edges1 [][]int, edges2 [][]int, k int) []int {n:=len(edges1)m:=len(edges2)g1:=make([][]int,n+1)g2:=make([][]int,m+1)solve(g1,edges1)solve(g2,edges2)mx:=0for i:=0;i<=m;i++ {t:=dfs(i,-1,0,g2,k-1)mx=max(mx,t)}v:=make([]int,n+1)for i:=0;i<=n;i++ {t:=dfs(i,-1,0,g1,k)v[i]=t+mx}return v
}
func solve(g [][]int,edges [][]int) {for _,e := range edges {x,y:=e[0],e[1]g[x]=append(g[x],y)g[y]=append(g[y],x)}
}func dfs(u int,fa int,d int,g [][]int,k int) int{if d>k {return 0}ans:=1for _,x:=range g[u] {if x!=fa {ans+=dfs(x,u,d+1,g,k)} }return ans
}