dgupta0812's blog

By dgupta0812, history, 4 years ago, In English

Hello everyone !!

Recently I was learning the Kosaraju's Algorithm for finding SCC's and after having learnt about it, I was wondering if we could traverse the transpose of the graph without actually reversing the edges (i.e., creating a new adjacency matrix). I couldn't come up with any solution so can anyone share their thoughts on how it can be done ?

  • Vote: I like it
  • +11
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You can reverse the topological sort instead

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I.m sorry, I don't see what we will be accomplishing by doing that. In Kosaraju's algorithm, we have to traverse over the transpose of the graph.

    If I am missing something, please correct me.

»
4 years ago, # |
  Vote: I like it +4 Vote: I do not like it

If you don't want to create two adjacency lists you can use Tarjan's algorithm instead, which finds SCCs with just one DFS.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you. I didn't knew there existed a simpler algorithm for SCC's.

»
4 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Build double edges and mark if its reserved edge or not, look at this:

define a graph:
vector<pair<int, int> > adj[MAXN];

addedge u->v:
adj[u].push_back(make_pair(v, 0))
adj[v].push_back(make_pair(u, 1))

go through edges from u:
for(auto v : adj[u]) {
  if(v.second == 0) {
    //original edge
  } else {
    //reserved edge
  }
}

or you can build two graphs:

define:
vector<int> org[MAXN], rev[MAXN];

addedge u->v
org[u].push_back(u);
rev[v].push_back(v);

go through original edges out of u:
for(int v : org[u]) {

}

go through reversed edges out of u:
for(int v : rev[u]) {

}