Monday, September 24, 2012

You have N computers and [Ca, Cb] means a is connected to b and this connectivity is symmetric and transitive. then write a program which checks that all computers are interconnected and talk two each other

I Believe there are multiple way to solve this problem 1. Here is my approach since graph is connected there will be path from each source to destination vertex , isn't it ? so we can simply run a dfs or bfs for all computers to check if all such path exist , finally we can return & of all operation that means all computer are inter connected and can talk to each other . PS.Since graph is undirected if there exist path from u to v then vice-verse also true so we wont calculate it again.

No comments :