NaoJoeMiao's blog

By NaoJoeMiao, 3 years ago, In English

The idea is to do a topsort on just directed edges, if there is a loop, then output NO.

If three is no loop, we can always find a solution. All we need to do is make sure the direction we add is following the top sort order.

So we assign an id for topsort results and use this determine which should come first.

You can view this question as adding more edges to a DAG and not creating loops, how to add those edges?

Things I learned:

  1. Use scanf printf and puts instead of cin/cout.

  2. memset is costly, not O(1). Avoid at all cost.

  3. Use BFS to do top sort instead of DFS to avoid stack overflow.

Submission

  • Vote: I like it
  • -2
  • Vote: I do not like it

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

Auto comment: topic has been updated by NaoJoeMiao (previous revision, new revision, compare).

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

Auto comment: topic has been updated by NaoJoeMiao (previous revision, new revision, compare).

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

Auto comment: topic has been updated by NaoJoeMiao (previous revision, new revision, compare).

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

Auto comment: topic has been updated by NaoJoeMiao (previous revision, new revision, compare).