Network and Graph theory problem

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

A time efficient algorithm is preferable.

---

This is called Graph Connectivity. Read about it and you can solve your problem.

---

Any search of the graph that doesn't traverse a node multiple times should be sufficient. There are many options: http://www.algorithmist.com/index.php/Graph_Connectivity I would probably pick DFS or BFS.

---

because you say that A time efficient algorithm is preferable.thus DFS is the best algorithm for U..notice that size of your edge in network computer is small dfs : http://en.wikipedia.org/wiki/Depth-first_search