data structures – find the strong component containing the vertex v

data structures – find the strong component containing the vertex v – Computer Science Stack Exchange

Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.

Anybody can ask a question

Anybody can answer

The best answers are voted up and rise to the top

Asked
today

Viewed
5 times

I’m trying to solve this question for practising purposes:

“Describe a linear-time algorithm for computing the strong component containing a given vertex v. On the basis of that algorithm, describe a simple quadratic-time algorithm for computing the strong components of a digraph.”

The question can be found here . It is question 31.

They give a couple of hints:

“Partial solution: To compute the strong component containing s

Find the set of vertices reachable from s

Find the set of vertices that can reach s

Take the intersection of the two sets

Using this as a subroutine, you can find all strong components in time proportional to t(E+V), where t is the number of strong components.”

My thoughts so far:

In order to find the vertices reachable from s, I can to DFS (or BFS, but will stick with DFS) from s. If n is the number of vertices and m is the number of edges this takes O(n+m) time, which seem fine for the purpose. I need to safe every discovered vertex somewhere. Not sure which datastructure works best for this. I will come back to this problem later.
In order to find all vertices that can reach s, I could bild/compute the reverse of the graph and to another DFS from a again. Computing the reverse of the graph should be O(n+m) and the DFS is O(n+m). So in total I have 3*O(n+m) which is just O(n+m). Of course the discovered vertices also need to be safed.
I’m not sure about how to build the intersection. Of course this is going to depend on how I saved the nodes before. So here are my ideas:

Building the intersection:

If I saved the nodes in two separate arrays (one for the first DFS and one for the second) I possibly could use a Hash-Table. This should be O(|firstNodes| + |secondNodes|) time. Maybe this would be ok, since O(|firstNodes| + |secondNodes|) is smaller than O(n+m), but it doesn’t seem optimal to me and it need extra space.
What if I mark the nodes I discoverd with the first DFS. Then I do the second DFS and check if nodes are already marked. If yes, I mark them “special” as belonging the the strong component? I wouldn’t have a list afterward that gives me the vertices of the strong component s belongs to but the strong component is still computed? For this approach I would need extra space at every node (in order to mark it).
In order to find all strong compoonents in time proportional to t(E+V) I could then to the same procedure on a vertex that is not yet marked as belonging to a strong component -> as long as there are such vertices, therefore t times. I would need to make sure, that every strong component is marked differently (e.g. increaing integers) and that the “I fould you” marks from the DFS are gone after each iteration (but not the marks for the strong components).