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
Google (yep, I won’t give you a link) about
Disjoint set union
@infinitepro I think we can also do it using connected components. Correct me if I am wrong.
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!