357. Count Other Nodes Reachable for Each Query

Count Other Nodes Reachable for Each Query

You are given an undirected graph that may contain several disconnected components and a list of node queries.

For each queried node, find how many other nodes are reachable from it. In other words, return the size of its connected component excluding the queried node itself.

Method Signature

List<Integer> countReachableNodes(int nodeCount, List<String> edges, List<Integer> queries)

Parameters

nodeCount is the number of nodes in the graph. The nodes are numbered from 0 to nodeCount - 1.
edges contains the undirected graph edges. Each edge is represented as "firstNode,secondNode".
queries contains the nodes for which the number of reachable nodes must be determined.

Return Value

Return a list where the value at index i is the number of other nodes reachable from queries.get(i). The results must follow the original order of the queries.

An isolated node has no other reachable nodes, so its result is 0.

Constraints

1 <= nodeCount <= 100,000
0 <= edges.size() <= 200,000
1 <= queries.size() <= 100,000
Every value in edges has the format "firstNode,secondNode".
0 <= firstNode < nodeCount
0 <= secondNode < nodeCount
0 <= queries.get(i) < nodeCount
The graph is undirected and may contain multiple disconnected components.
Each edge contains exactly one comma and no spaces.
Duplicate edges and self-loops may appear and do not change reachability.
q = queries.size()

Examples

Example 1

countReachableNodes(nodeCount = 7, edges = List.of("0,1", "1,2", "3,4", "4,5"), queries = List.of(0, 3, 6, 2))

Output: List.of(2, 2, 0, 2)

Nodes 0, 1, and 2 form one component, while nodes 3, 4, and 5 form another. Node 6 is isolated.

Example 2

countReachableNodes(nodeCount = 6, edges = List.of("0,1", "1,2", "2,3", "3,0", "4,5"), queries = List.of(1, 4, 5))

Output: List.of(3, 1, 1)

Node 1 can reach the other three nodes in its component. Nodes 4 and 5 can each reach only the other node in their component.

Example 3

countReachableNodes(nodeCount = 4, edges = List.of(), queries = List.of(0, 2, 2, 3))

Output: List.of(0, 0, 0, 0)

The graph has no edges, so every node is isolated. Repeated queries are evaluated independently and produce the same result.