奇网企业网站管理系统,织梦大气绿色大气农业能源化工机械产品企业网站源码模版,网站的可用性,资源猫题目描述
现有一棵由 n 个节点组成的无向树#xff0c;节点编号从 0 到 n - 1 #xff0c;共有 n - 1 条边。
给你一个二维整数数组 edges #xff0c;长度为 n - 1 #xff0c;其中 edges[i] [ai, bi] 表示树中节点 ai 和 bi 之间存在一条边。另给你一个整数数组 restr…题目描述
现有一棵由 n 个节点组成的无向树节点编号从 0 到 n - 1 共有 n - 1 条边。
给你一个二维整数数组 edges 长度为 n - 1 其中 edges[i] [ai, bi] 表示树中节点 ai 和 bi 之间存在一条边。另给你一个整数数组 restricted 表示 受限 节点。
在不访问受限节点的前提下返回你可以从节点 0 到达的 最多 节点数目。
注意节点 0 不 会标记为受限节点。
示例 1 输入n 7, edges [[0,1],[1,2],[3,1],[4,0],[0,5],[5,6]], restricted [4,5]
输出4
解释上图所示正是这棵树。
在不访问受限节点的前提下只有节点 [0,1,2,3] 可以从节点 0 到达。
示例 2 输入n 7, edges [[0,1],[0,2],[0,5],[0,4],[3,2],[6,5]], restricted [4,2,1]
输出3
解释上图所示正是这棵树。
在不访问受限节点的前提下只有节点 [0,5,6] 可以从节点 0 到达。
解题思路
本题并不难解题主要是抓住题意因为受限节点不可以访问所以我们可以直接将受限节点涉及到的边直接排除在外而后在验证节点是否受限时如果一个个查显然时间复杂度过高这时我们可以使用Set减少查询的时间复杂度。而后进行一次dfs就可以了而后我们还需要知道因为这是一棵树所以节点不会重复访问所以我们直接即可。
代码如下
class Solution {int cnt0;public int reachableNodes(int n, int[][] edges, int[] restricted) {SetInteger setnew HashSetInteger();ListInteger lists[]new ArrayList[n];for(int i:restricted)//存入setset.add(i);for(int i0;in;i)lists[i]new ArrayList();for(int i0;in-1;i){int xedges[i][0];int yedges[i][1];if(set.contains(x)||set.contains(y))//不进行边加入continue;lists[x].add(y);lists[y].add(x);}boolean flag[]new boolean[n];flag[0]true;dfs(0,lists,flag);return cnt;}public void dfs(int p,ListInteger lists[],boolean flag[]){cnt;//不会重复直接ListInteger listlists[p];for(int i0;ilist.size();i){int llist.get(i);if(!flag[l]){flag[l]true;dfs(l,lists,flag);flag[l]false;}}}
}
