icpc_expert's blog

Converting Cyclic graph into Acyclic
By icpc_expert, history, 6 years ago, In English

Can anybody explain me how to convert Cyclic graph into Acyclic Graph with different layers.

  • Vote: I like it
  • 0
  • Vote: I do not like it

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

Strong name to post content. :P

Anyways, check "SCC Condensation". You can condense all SCC's of the graph, and create a directed one where each node represents a SCC. Edges exist between 2 SCC's if a node in the first SCC goes to the second in the original graph. This is of course only useful if the nature of your problem allows you to abstract the graph into that.

e-maxx article : https://cp-algorithms.com/graph/strongly-connected-components.html

→ Reply