your 1st Q: for each vertex run a dfs and count the number of vertices it can reach O( V^2 + VE )
another solution would be using an algorithm similar to floyd-warshal O(V^3) a[src][dest] is true if there is an edge src->dest for (k=0;k<n;k++) for (i=0;i<n;i++) for (j=0;j<n;j++) if (a[i][k] && a[k][j]) a[i][k]=true; now a[src][dest] is true if there is path from src to dest now we just need to count the number of reachable vertices for each vertex your 2nd Q: Anand is right! :) -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
