2024.3.2力扣每日一题——受限条件下可到达节点的数目

题目来源

力扣每日一题；题序：2368

我的题解

方法一 深度优先搜索

使用深度优先搜索实现，在搜索过程中根据restricted进行截停。

时间复杂度：O(n)
空间复杂度：O(n)

int res=0;
public int reachableNodes(int n, int[][] edges, int[] restricted) {List<Integer>[] g=createTree(n,edges);boolean[] bRestricted=new boolean[n];for(int i:restricted){bRestricted[i]=true;}dfs(g,0,-1,bRestricted);return res;
}
public List<Integer>[] createTree(int n,int[][] edges){List<Integer>[] g=new ArrayList[n];for(int i=0;i<n;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(List<Integer>[] 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[] bRestricted=new boolean[n];for(int i:restricted){bRestricted[i]=true;}UF uf=new 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){count=n;parent=new int[n];for (int i = 0; i < n; i++) {parent[i]=i;}}public void union(int p,int q){int parentP=find(p);int parentQ=find(q);if (parentP==parentQ)return;parent[parentQ]=parentP;count--;}public boolean isConnection(int p,int q){int parentP=find(p);int parentQ=find(q);return parentP==parentQ;}public int find(int x){if(parent[x]!=x){parent[x]=find(parent[x]);//路径压缩}return parent[x];}public int getCount(){int cnt=0;//找0所在的集合int rt=find(0);for(int i=0;i<parent.length;i++){if(rt==find(i))cnt++;}return cnt;}
}

有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈😄~