Maximum no. of nodes reachable from a given source in a Graph

Question

I have a directed graph in which each node has exactly one edge, to one other node. I have to find the node from which the maximum number of nodes can be reached.

I tried to do it using a dfs, and store the information in the array sum[] but I get segmentation faults. The graph is represented as an adjacency List of pair< int, int >. First is the destination, and second is the weight. In this problem weight = 0.

My dfs implementation:

int sum[V];   // declared globally, initially set to 0
bool visited[V];   // declared globally, initially set to false

int dfs( int s ){

    visited[s]= true;

    int t= 0;

    for( int i= 0; i< AdjList.size(); ++i ){

        pii v= AdjList[s][i];

        if( visited[v.first] )
            return sum[v.first];

        t+= 1 + dfs( v.first );
    }

    return sum[s]= t;
}

Inside main():

int maxi= -1;    // maximum no. of nodes that can be reached

for( int i= 1; i<= V; ++i ){   // V is total no. of Vertices

    int cc;

    if( !visited[i] )
        cc= g.dfs( i ) ;

    if( cc > maxi ){
        maxi= cc;
        v= i;
    }
}

And the graph is :

1 2    /* 1---->2 */
2 1    /* 2---->1 */
5 3    /* 5---->3 */
3 4    /* 3---->4 */
4 5    /* 4---->5 */

What is be the problem in my dfs implementation?

Answer 1

You exit your dfs when you find any node that was already reached, but I have the impresion that you should run through all adjectent nodes: in your dfs function change the if statement inside for loop:

instead:

if(visited[v.first] )
  return sum[v.first];

t+= 1 + dfs( v.first );

---

if(!visited[v.first] ) {
  t+= dfs( v.first );
}

and initialize t with 1 (not 0). This way you will find size of connected component. Because you are not interested in the node from which you started then you have to decrease the final result by one.

There is one more assumption that I made: your graph is undirected. If it's directed then if you are interested in just solving the problem (not about complexity) then just clear visited and sum array after you are done with single run of dfs in main function.

---

EDIT

One more error in your code. Change:

for( int i= 0; i< AdjList.size(); ++i ){

into:

for( int i= 0; i< AdjList[s].size(); ++i ){

You should be able to trace segfault by yourself. Use gdb it's really usefull tool.