Graph reachability Ques

Let the graph vertices are numbered from 1 to |V|.....let
min(i)=min number of the vertex reachable from vertex number i
example- let from vertex 2 i can reach to vertex number 1,5,6....so min(2)=1....
give an algorithm to find min(i) for all the vertices of the graph....

Achi time complexity mei nikalna....

Can b solved in O(n) time.

------------------------------

Code:


Take a MinArray[n] to store the Min Result.
Initialize MinArray[i=(0 to n-1)] to some MAX value;

for( i in V[Graph] )
{
      call mod-DFS(i);
}

print Array[i=(0 to n-1)]


------------------------------

Code:


int mod-DFS( int i )
{
      if( color[i]==0 ) //checks if we're not done with i'th vertex
      {
            color[i] = 1;
            for( every possible vertex j from i )
            {
                      if(color[i]==1)
                                  MinArray[i] = minimum( MinArray[i],  j );
                      else
                                  MinArray[i] = minimum( MinArray[i],  j,  mod-DFS(j) );
            }
            color[i] = 2;
      }
    return MinArray[i];
}


shivang sir bataiye sahi hai ya galat

Here I assume that, if I can go from i'th node to j'th node,
such that ( i < j ) is true, So the answer should not be 'i' but 'j'.
i.e. ( MinArray[i] = j ) in this case.

the other way, i.e. if I want to have ( MinArray[i] = i ) in the above case
I could have modified some of the lines as ..

Code:


Initialize { MinArray[i=(0 to n-1)] = i  };


and

Code:


for( every possible vertex j from i )
{
                      if(color[i]==1)
                                  MinArray[i] = minimum( MinArray[i],  j );
                      else
                                  MinArray[i] = minimum( MinArray[i],  mod-DFS(j) );
}


That's It.