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

Problem: 2368. 受限条件下可到达节点的数目

文章目录

• 思路
• 复杂度
• Code

  思路

  👨‍🏫 灵神

  复杂度

  时间复杂度: O ( n ) O(n) O(n)

  空间复杂度: O ( n ) O(n) O(n)

  Code

  class Solution {
  	int ans = 0;
  	boolean[] set;
  	List[] es;
  	public int reachableNodes(int n, int[][] edges, int[] restricted)
  	{
  		es = new ArrayList[n];
          Arrays.setAll(es, x->new ArrayList());
  		set = new boolean[n];
  		for (int[] e : edges)
  		{
  			int a = e[0];
  			int b = e[1];
  			es[a].add(b);
  			es[b].add(a);
  		}
  		for (int x : restricted)
  			set[x] = true;
  		dfs(0);
  		return ans;
  	}
  	private void dfs(int x)
  	{
  		if (set[x])
  			return;
  		ans++;
          set[x] = true;
  		for (int y : es[x])
  			dfs(y);
  	}
  }