CSES Solutions – Reachable Nodes
A directed acyclic graph consists of n nodes and m edges. The nodes are numbered 1,2,…,n.
Calculate for each node the number of nodes you can reach from that node (including the node itself).
Examples:
Input: n = 5, m = 6, edges = {{1, 2}, {1, 3}, {1, 4}, {2, 3}, {3, 5}, {4, 5}}
Output: 5 3 2 2 1
Explanation:
- From node 1, we can reach nodes 1, 2, 3, 4 and 5.
- From node 2, we can reach nodes 2, 3 and 5.
- From node 3, we can reach nodes 3 and 5.
- From node 4, we can reach nodes 4 and 5.
- From node 5, we can reach only node 5.
Input: n = 6, m = 10, edges = {{1, 2}, {2, 3}, {2, 3}, {2, 4}, {1, 4}, {2, 4}, {1, 5}, {4, 5}, {5, 6}, {1, 6}}
Output: 6 5 1 3 2 1
Explanation:
- From node 1, we can reach nodes 1, 2, 3, 4, 5 and 6.
- From node 2, we can reach nodes 2, 3, 4, 5 and 6.
- From node 3, we can reach only node 3.
- From node 4, we can reach nodes 4, 5 and 6.
- From node 5, we can reach nodes 5 and 6.
- From node 6, we can reach only node 6.
Approach:
We can find the number of reachable nodes from every node by starting from the nodes which has 0 out-degree as those nodes will have only one reachable node and that is the node itself. After visiting all the nodes which have 0 out-degree, we can update the outdegree of the parent nodes and move to those parent nodes whose outdegree has now been updated to 0 and find the reachable nodes from those parent nodes. Reachable nodes from the parent nodes will be the parent node + all the nodes which are reachable by any of its children.
In order to keep track of the reachable nodes, we will keep a bitset for every node, where the ith bit of the current bitset is set if we can reach ith node from the current node. And to find the parent of the node with outdegree 0, we can simply reverse the edges of the graph (construct transpose of the graph)and use indegree and Kahn’s algorithm to maintain the order of nodes.
Below is the implementation of the algorithm:
#include <bits/stdc++.h>
using namespace std;
const int maxN = 50001;
bitset<maxN> ans[maxN];
vector<int> adj[maxN + 1];
int main()
{
// Sample Input
int n = 5, m = 6;
vector<vector<int> > edges
= { { 1, 2 }, { 1, 3 }, { 1, 4 },
{ 2, 3 }, { 3, 5 }, { 4, 5 } };
// vector to store the indegree of transpose graph
int indeg[n + 1] = {};
// Store the rreverse edges along with the indegrees
for (int i = 0; i < edges.size(); i++) {
adj[edges[i][1]].push_back(edges[i][0]);
indeg[edges[i][0]] += 1;
}
// queue to keep track of all nodes with indegree = 0
queue<int> q;
for (int i = 1; i <= n; i++) {
if (indeg[i] == 0) {
// Set the ith bit of bitset of node i
ans[i].set(i);
// Push the ith node to the queue
q.push(i);
}
}
// Iterate till the queue is not empty
while (!q.empty()) {
int u = q.front();
q.pop();
// Visit all the neighbours of the current node
for (int v : adj[u]) {
// Use the reachable nodes of the children to
// mark the reachable nodes of the current node
ans[v] |= ans[u];
indeg[v]--;
// If the indegree of the neighbouring nodes
// become 0, push the neighbouring node to the
// queue
if (indeg[v] == 0) {
ans[v].set(v);
q.push(v);
}
}
}
// The count of reachable nodes of ith node is the
// number of set bits in ith bitset
for (int i = 1; i <= n; i++)
cout << ans[i].count() << " ";
}
import java.util.*;
public class ReachableNodes {
public static void main(String[] args)
{
// Sample Input
int n = 5, m = 6;
int[][] edges = { { 1, 2 }, { 1, 3 }, { 1, 4 },
{ 2, 3 }, { 3, 5 }, { 4, 5 } };
// Vector to store the indegree of transpose graph
int[] indeg = new int[n + 1];
// Adjacency list to store the reverse edges
List<Integer>[] adj = new ArrayList[n + 1];
for (int i = 0; i <= n; i++) {
adj[i] = new ArrayList<>();
}
// Store the reverse edges along with the indegrees
for (int[] edge : edges) {
adj[edge[1]].add(edge[0]);
indeg[edge[0]] += 1;
}
// Queue to keep track of all nodes with indegree =
// 0
Queue<Integer> q = new LinkedList<>();
BitSet[] ans = new BitSet[n + 1];
for (int i = 0; i <= n; i++) {
ans[i] = new BitSet(n + 1);
}
// Initialize the bitsets and the queue
for (int i = 1; i <= n; i++) {
if (indeg[i] == 0) {
// Set the ith bit of bitset of node i
ans[i].set(i);
// Push the ith node to the queue
q.add(i);
}
}
// Iterate till the queue is not empty
while (!q.isEmpty()) {
int u = q.poll();
// Visit all the neighbours of the current node
for (int v : adj[u]) {
// Use the reachable nodes of the children
// to mark the reachable nodes of the
// current node
ans[v].or(ans[u]);
indeg[v]--;
// If the indegree of the neighbouring nodes
// becomes 0, push the neighbouring node to
// the queue
if (indeg[v] == 0) {
ans[v].set(v);
q.add(v);
}
}
}
// The count of reachable nodes of ith node is the
// number of set bits in ith bitset
for (int i = 1; i <= n; i++) {
System.out.print(ans[i].cardinality() + " ");
}
}
}
// This code is contributed by shivamgupta0987654321
from collections import defaultdict, deque
maxN = 50001
def main():
n = 5
m = 6
edges = [[1, 2], [1, 3], [1, 4], [2, 3], [3, 5], [4, 5]]
ans = [set() for _ in range(n + 1)]
adj = defaultdict(list)
indeg = [0] * (n + 1)
for edge in edges:
adj[edge[1]].append(edge[0])
indeg[edge[0]] += 1
q = deque()
for i in range(1, n + 1):
if indeg[i] == 0:
ans[i].add(i)
q.append(i)
while q:
u = q.popleft()
for v in adj[u]:
ans[v] |= ans[u]
indeg[v] -= 1
if indeg[v] == 0:
ans[v].add(v)
q.append(v)
for i in range(1, n + 1):
print(len(ans[i]), end=" ")
if __name__ == "__main__":
main()
class ReachableNodes {
static main() {
// Sample Input
let n = 5, m = 6;
let edges = [ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ],
[ 2, 3 ], [ 3, 5 ], [ 4, 5 ] ];
// Array to store the indegree of transpose graph
let indeg = new Array(n + 1).fill(0);
// Adjacency list to store the reverse edges
let adj = new Array(n + 1);
for (let i = 0; i <= n; i++) {
adj[i] = [];
}
// Store the reverse edges along with the indegrees
for (let edge of edges) {
let [u, v] = edge;
adj[v].push(u);
indeg[u] += 1;
}
// Queue to keep track of all nodes with indegree = 0
let q = [];
let ans = new Array(n + 1);
for (let i = 0; i <= n; i++) {
ans[i] = new BitSet(n + 1);
}
// Initialize the bitsets and the queue
for (let i = 1; i <= n; i++) {
if (indeg[i] === 0) {
// Set the ith bit of bitset of node i
ans[i].set(i);
// Push the ith node to the queue
q.push(i);
}
}
// Iterate till the queue is not empty
while (q.length !== 0) {
let u = q.shift();
// Visit all the neighbours of the current node
for (let v of adj[u]) {
// Use the reachable nodes of the children to
// mark the reachable nodes of the current node
ans[v].or(ans[u]);
indeg[v]--;
// If the indegree of the neighbouring nodes
// becomes 0, push the neighbouring node to the
// queue
if (indeg[v] === 0) {
ans[v].set(v);
q.push(v);
}
}
}
// Print the desired output format
let output = "";
for (let i = 1; i <= n; i++) {
output += ans[i].cardinality() + " ";
}
console.log(output.trim());
}
}
// Define BitSet class
class BitSet {
constructor(size) {
this.bits = new Array(size).fill(0);
}
set(index) {
this.bits[index] = 1;
}
or(otherBitSet) {
for (let i = 0; i < this.bits.length; i++) {
this.bits[i] = this.bits[i] | otherBitSet.bits[i];
}
}
cardinality() {
return this.bits.reduce((count, bit) => count + bit, 0);
}
}
// Call the main function
ReachableNodes.main();
output :
5 3 2 2 1
Time Complexity: O(n + m)
Auxiliary Space: O(n + m)