I am new to graphs and i am stuck in this question at hackerearth. Basically we have to see if two nodes are interconnected or not but we cant use bfs function in each query because of the time complexity. Please help!

That’s very easy to check.

```
int val=0;
int checkconnection[graph size]
for node x in graph
if not visited x
for node y in bfs(x)
checkconnection[y]=val
mark y visited
val+=1
```

Now all connected nodes will have same value in `checkconnection`

Google (yep, I won’t give you a link) about `Disjoint set union`

read up on DSU.

It’s same thing

simply perform dfs until all the nodes get exhausted and assign group no.s to each .

if in the query they belong to different groups then disconnected else connected

Thanks. Found what i needed!