How do we know 2 nodes are connected in a graph or not?

general
, , , ,
1

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!

2

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

3

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

4

@infinitepro I think we can also do it using connected components. Correct me if I am wrong.

5

read up on DSU.
It’s same thing

6

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

7

Thanks. Found what i needed!