Question

Someone says "All roads lead to Rome"! Given a directed graph Q (you can assume that Q has no self-loops), define a Rome node RN to be a node m in Q such that: there is an edge from x to m for every node x != m in Q and m has no outgoing edges.

n is the number of nodes in our graph Q, assume that the graph structure is stored in an adjacency matrix.

what is a O(n) or O(n^2) algorithm for finding whether or not Q has a Rome node N? Explain why this algorithm has complexity that it does.

What other info is needed? This is all that is provided

Again, there is no other info, so "more info" does not tell me what else needs to be provided, I need to know what else is needed, this is all I have

Answer 1

As directly stated in the question : m is a Rome Node iff  there is an edge from x to m for every node x != m in Q and m has no outgoing edges.

We can use the above condition to check all possible Nodes and see if the fill up the criterion of a Rome Node or not. Let the abobe requirements be broken into 2 conditions.

Condition 1 : All nodes i (except m) has a directed edge to m.

Condition 2 : There are no directed edge coming out of m.

Since , we are given the Graph Q in the form of an adjacency matrix , a simple row and column check algorithm for all possible nodes would suffice the need.

Property of an Adjacency Matrix : -

A[i][j] = 1 => Edge from i to j.

A[i][j] = 0 => No Edge from i to j.

Using the above 2 conditions and the Property of Adjacency matrix , the checking can be done in the following manner.

Satisfying Condition 1 :   A Node m satisfies condition 1 when

A[1][m] = A[2][m] = A[3][m] = ..... =A[m-1][m] = A[m+1][m] = ........=A[N-1][m] = A[N][m] = 1

=>

Satisfying Condition 2 : A Node m satisfies condition 2 when

A[m][1] = A[m][2] = A[m][3] = ..... = ........=A[m][N-1] = A[m][N] = 0

=>

Using the above 2 condition satisfactions , this can be applied on each node starting from 1 to N , and return the solution when any such Node is found.

Here is the pseudocode for the same.

Input - Graph Q , Adj. Matrix A[N][N]
function findRomeNode()
     /* Initialise with -1 when No such Nodes exist */
     int node = -1;
     /* Traverse through each currentNode from 1 to N */ 
     for(int currNode : 1 to N)
     begin for
          /* Initialise Sum of Condn1 and Condn2 as 0 */
          int sum1 = 0 , sum2 = 0
          /* Traverse the currentNode column and check if there are N-1 edges incoming*/
          for(int i : 1 to N)
          begin for
               sum1 = sum1 + Adj[i][currNode];
          end for
           /* Traverse the currentNode row and check if there are 0 edges outgoing*/
          for(int i : 1 to N)
          begin for
               sum2 = sum2 + Adj[currNode][i];
          end for
          /* Return the answer if both the cond1 and condn 2 are satisfied */
          if(sum1 equals N-1 AND sum2 equals 0)
          begin if
               return currNode;
          end if
     end for
     /* When no such node exist */
     return node;
end function

The above algorithm has a O(N²) time complexity . The complexity is like this because in the worst case when no solution exists , we traversed 1 entire row and 1 entire column for each node.

Traversing 1 entire row and 1 entire column = 2N operations.

This was done for all N Nodes , hence 2N*N = 2N² operations.

Therefore, the time complexity is O(N²)