Блог пользователя dgupta0812

Автор dgupta0812, история, 4 года назад, По-английски

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 ?

  • Проголосовать: нравится
  • +11
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

You can reverse the topological sort instead

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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]) {

}