You’re given a directed graph with N nodes, and M edges. On this graph, you need to compute for each node u, the number of nodes v that are reachable from it (including itself).
You’re given a directed graph with N nodes, and M edges. On this graph, you need to compute for each node u, the number of …
Share
#include <bits/stdc++.h> using namespace std; signed main() { int n, m, a, b; cin >> n >> m; vector<int> start(n); vector<vector<int>> adj(n); bitset<50000> ans[n]; for(int i = 0; i < m; i++) { cin >> a >> b; adj[b - 1].push_back(a - 1); start[a - 1]++; } queue<int> q; for(int i = 0; i < n; i++) { if(start[i]) continue; ans[i].set(i); q.push(i); } while(!q.empty()) { int node = q.front(); q.pop(); for(int child: adj[node]) { ans[child] |= ans[node]; start[child]--; if(start[child] == 0) { ans[child].set(child); q.push(child); } } } for(int i = 0; i < n; i++) cout << ans[i].count() << " "; cout << '\n'; }