-
Notifications
You must be signed in to change notification settings - Fork 0
/
Reachable Nodes
51 lines (42 loc) · 1 KB
/
Reachable Nodes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <bits/stdc++.h>
void BFS(int sv , vector <int> adj[] , vector <int> &vis , vector <int> &nodes , int n , int m)
{
queue <int> q ;
q.push(sv) ;
vis[sv] = 1 ;
while(!q.empty())
{
int f = q.front() ;
nodes.push_back(f) ;
q.pop() ;
for(auto itr : adj[f] )
{
if (!vis[itr]) {
q.push(itr);
vis[itr] = 1;
}
}
}
}
vector<int> countNodes(int n, int m, vector< vector<int> > & edges)
{
vector <int> adj[n] ;
for(int i = 0 ; i < edges.size() ; i++)
{
adj[edges[i][0]].push_back(edges[i][1]) ;
adj[edges[i][1]].push_back(edges[i][0]) ;
}
vector <int> ans(n , 0);
vector <int> vis(n , 0);
for (int i = 0; i < n; i++) {
vector <int> nodes ;
if(vis[i] == false)
BFS(i, adj, vis, nodes, n, m);
for(int i = 0 ; i < nodes.size() ; i++)
{
ans[nodes[i]] = nodes.size() ;
}
}
return ans ;
// Write your code here.
}