Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

WalidMasri's blog

Directed Graphs into DAG
By WalidMasri, history, 10 years ago, In English

Hello everyone!

Having found the SCC of a directed graph G, how can I contract each SCC to a single node?

Thanks.

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

Comments Comments (14)
| Write comment?
»
10 years ago, hide # |
 
Vote: I like it +6 Vote: I do not like it

Suppose you know C[v] — which component contains node v.
Now you scan through edges of the original graph, let current one be x->y.
Then you should add an edge C[x]->C[y] in compressed graph if C[x] is not equal to C[y].

→ Reply
  • »
    »
    10 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Yes, and you should also remember to mark which edges have already been added so you don't double count any edge. You can use a boolean array or an edge set

    → Reply
    • »
      »
      »
      10 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      What's so bad about keeping a multi-edge in DAG? :P

      → Reply
      • »
        »
        »
        »
        10 years ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it

        If we have to do some traversal in the compressed graph we are going to waste some operations while scanning the adjacency list of each vertex :P

        → Reply
    • »
      »
      »
      10 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      I'd rather use disjoint sets. It doesn't require too much memory and I think it's faster than an edge set :D and are VERY easy to code

      → Reply
      • »
        »
        »
        »
        10 years ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it

        How can i use disjoint sets for this purpose? I have never seen this application, i usually use DSU for Kruskal's only :P

        → Reply
      • »
        »
        »
        »
        10 years ago, hide # ^ |
        ← Rev. 2  
        Vote: I like it 0 Vote: I do not like it

        Other valid option would be using a hash function so you can check in O(1) whether the edge exists or not! It should be easy to come up with a function that wont generate collisions since amount of edges is usually small :)

        EDIT : never used unordered set, but this may actually be the implementation of what i said above

        → Reply