Network and Graph theory problem

Question

You have N computers and [Ca, Cb] means a is connected to b 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.

Answer 1

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

Answer 2

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.