邯郸网站制作外包,wordpress写简历,个人软件制作网站,做京东网站的摘要2024.3.2 题目来源我的题解方法一 深度优先搜索方法二 并查集 题目来源
力扣每日一题#xff1b;题序#xff1a;2368
我的题解
方法一 深度优先搜索 使用深度优先搜索实现#xff0c;在搜索过程中根据restricted进行截停。 时间复杂度#xff1a;O(n) 空间复杂度#… 2024.3.2 题目来源我的题解方法一 深度优先搜索方法二 并查集 题目来源
力扣每日一题题序2368
我的题解
方法一 深度优先搜索 使用深度优先搜索实现在搜索过程中根据restricted进行截停。 时间复杂度O(n) 空间复杂度O(n) int res0;
public int reachableNodes(int n, int[][] edges, int[] restricted) {ListInteger[] gcreateTree(n,edges);boolean[] bRestrictednew boolean[n];for(int i:restricted){bRestricted[i]true;}dfs(g,0,-1,bRestricted);return res;
}
public ListInteger[] createTree(int n,int[][] edges){ListInteger[] gnew ArrayList[n];for(int i0;in;i){g[i]new ArrayList();}for(int[] t:edges){int from t[0];int to t[1];g[from].add(to);g[to].add(from);}return g;
}
public void dfs(ListInteger[] g,int cur,int pre,boolean[] bRestricted){res;for(int next:g[cur]){//防止循环遍历 并且不能是受限节点if(next!pre!bRestricted[next])dfs(g,next,cur,bRestricted);}
}方法二 并查集 如果忽略受限的点树就会变成若干个连通块要计算的就是 0号点所在连通块的大小。 因此可以用并查集来不断地将点集进行合并依次考虑每一条边如果边上两个点都没有受限那么合并这两个点的所在集合否则跳过该边。最终查询 0号点所在连通块的大小即可。 时间复杂度O(n×α(n))其中 n 是无向树中点的个数α是反阿克曼函数。使用路径压缩和按秩合并优化后的并查集单次查询和合并操作的时间复杂度是 O(α(n))通常比较小可以忽略。 空间复杂度O(n) public int reachableNodes(int n, int[][] edges, int[] restricted) {boolean[] bRestrictednew boolean[n];for(int i:restricted){bRestricted[i]true;}UF ufnew UF(n);for(int[] v:edges){//如果起始和结束节点有一个是受限的节点则不合并if(bRestricted[v[0]]||bRestricted[v[1]]){continue;}uf.union(v[0],v[1]);}return uf.getCount();
}
class UF{private int count;private int parent[];public UF(int n){countn;parentnew int[n];for (int i 0; i n; i) {parent[i]i;}}public void union(int p,int q){int parentPfind(p);int parentQfind(q);if (parentPparentQ)return;parent[parentQ]parentP;count--;}public boolean isConnection(int p,int q){int parentPfind(p);int parentQfind(q);return parentPparentQ;}public int find(int x){if(parent[x]!x){parent[x]find(parent[x]);//路径压缩}return parent[x];}public int getCount(){int cnt0;//找0所在的集合int rtfind(0);for(int i0;iparent.length;i){if(rtfind(i))cnt;}return cnt;}
}有任何问题欢迎评论区交流欢迎评论区提供其它解题思路代码也可以点个赞支持一下作者哈~
