CareerCup

It is a graph and do a BFS on the graph starting from any node and see if the count of nodes is N or not ... If the count is N, then it means that all the computers are interconnected ...

:D its a high time for Ms Gayle to add 'like' button for people comments :D

The question is unclear. What does "all computers are interconnected" mean? Each computer has a direct connection to every other computer? OR, there is a path of communication (possibly involving intermediate computers) between any two?

Comment by Rushabh addresses the second interpretation.

I think Warshall's algorithm for transitive closure would be a good solution...

I think Warshall's algorithm for transitive closure would be a good solution...

Rushabh is right. Its a graph, just do a bfs or dfs to see if you can visit all the N nodes. This takes O(N+E) (where N is the number of vertices and E is the number of edges)
Warshall's algo would work. But it takes more time. Warshall's takes O(N^3).

The key idea here is to exploit the symmetricity and transitivity of connectivity between two computers.

So c(a,b) => c(b,a) (symmetric)
Also , c(x,y) and c(y,z) => c(x,z)

Now let's say we have n computers. Check if c(i,n) is true for all i = n-1,n-2,......1. If there's at least one i for which c(i,n) is false, the computers are not interconnected. Otherwise they are.

Pseudocode

isConnected(){
for( i= n-1 ... 1){
if(c(i,n)==TRUE){
continue;
}else
return FALSE
}
return TRUE;
}
Time complexity -> O(n)

Correctness of the algorithm:

The algo starts with checking c(n-1,n). If this is true,we go to the next step in which we check if c(n-2,n). If that is also true,we CLAIM that c(n-2,n-1) is also true.(Why?) Because c(n-1,n) = T

=> c(n,n-1) =T (symmetric property).
Also c(n-2,n)= T.

So by the transitivity property,c(n-2,n-1)=T

Let's now evaluate c(n-3,n). If that's also true,again we can claim that c(n-3,n-2) and c(n-3,n-1) are also true. How? Well,using the same logic,we have the following

if c(n-3,n) = T we already know that c(n-1,n),c(n-2,n-1),c(n-2,n) are all true,otherwise the algo would have exited by now)

We claim that c(n-3,n-2),c(n-3,n-1) are also true.Reason out why.

Similarly we can establish the connectivity of any two computers in the given set.

The above pseudocode is wrong . Consider this case : n is connected to n-2 , n-1 is connected to n-2. By transitivity , n is connected to n-1.
But, acc to the pseudocode, n is not connected directly to n-1 so the program will exit and false will be returned - Which is wrong

The above pseudocode is wrong . Consider this case : n is connected to n-2 , n-1 is connected to n-2. By transitivity , n is connected to n-1.
But, acc to the pseudocode, n is not connected directly to n-1 so the program will exit and false will be returned - Which is wrong

Oh yeah..Thanks for pointing that out. I was just trying to avoid the formal graph based approach.

So,then the given information of direct connectivity between two computers could be translated into an undirected graph using the adjacency list/matrix representation.

The problem then reduces to finding whether the graph so formed is connected. A standard DFS could be used to do that.I don't think a complete transitive closure determination using warshall's algo is required here.

Take a node_counter to count the node's, and initially mark its value 0;

void checkConnectivity(node * current_node)
{
   if(ptr == 0)
      return;
   
   loop for each conneced children_node from the current_node.
   {
      if(the children_node is not visited yet)
      {
         1. mark the node as visited.
         2. increment the node_counter by one.
         3. recursive call the checkConnectivity(children_node) 
      }
   }
}

If the node_counter == num of nodes in graph
  then nodes are interconnected
else
  nodes are not interconnected

Take a node_counter to count the node's, and initially mark its value 0;

void checkConnectivity(node * current_node)
{
   if(ptr == 0)
      return;
   
   loop for each conneced children_node from the current_node.
   {
      if(the children_node is not visited yet)
      {
         1. mark the node as visited.
         2. increment the node_counter by one.
         3. recursive call the checkConnectivity(children_node) 
      }
   }
}

If the node_counter == num of nodes in graph
  then nodes are interconnected
else
  nodes are not interconnected

Minimum Spanning Tree.

All you need to check if the graph is connected OR not,

WTF, you people are wasting time ...its pretty simple... just check for graph connectivity using DFS/BFS and you're done!
first solution by Rusabh is OK, rest people are just repeating the same things...sux man...

isn't a disjointed set enough?

This can be easily checked for N computers whether they are connected by above rules,they must have N*(N-1)/2 distinct connection pairs(i.e. C[i,j] & C[j,i] are counted one time only)Now simply check whether given connection pair count is equal to N*(N-1)/2. if it is less than than certainly some disconnected computers are there. complexity: O(1)