Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

### etal's blog

By etal, 6 years ago, ,

As you know, given a directed graph there are several algorithms that efficiently divide the graph into Strongly Connected Components. Once you have them you can construct a new graph where each vertex corresponds to a SCC and there is a directed edge from u to v iff there exists an edge that goes from a vertex in SCC u to SCC v. Do you know a way to create the adjacency list of this new graph efficiently stored in a vector<vector>?

The only solution I've come up with is doing a vector<set > G and forall edge (a->b) in the old graph inserting comp[b] in G[comp[a]] and once you've done that copy the set into a vector<vector >.

Thank you!

• +4

 » 6 years ago, # | ← Rev. 2 →   +6 Here is an alternative: fill(mark, false) for c in components for v in c for u in original_edges(v) if non mark[comp(u)] add_comp_edge(c, comp(u)) mark[comp(u)] = true for v in c for u in original_edges(v) mark[comp(u)] = false 
 » 6 years ago, # | ← Rev. 2 →   +8 O(V+E) code