The_Royalty's blog

Problem with SCC
By The_Royalty, 10 years ago, In English

Hello, I've been trying to solve this problem Jobbery but my code gets TLE on test 50.

Could someone help me to improve my algorithm? I think it's O(M+N) because I'm using Tarjan's algorithm

My code

Thanks

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

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Nobody?

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

What you have written does not look like a linear algorithm. To understand what is wrong with it, please explain as clearly as you can (at least to yourself) what the lines 63 – 71 do and — specifically — what purpose the variable S serves.

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

    Isn't it just a stack, that will have at most n elements pushed and hence at most n elements popped?

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

      My bad, I somewhy thought that the array vis is used to call dfs(u).

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

    It's an implementation of Tarjan's algorithm taken from Competitive Programming 3 book.

    I will comment my codes for future questions. Thanks

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

stupid site -_-, I'm still waiting for some judge ID to submit the problem !!

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Oh, but it passes :). Just change cin,cout to scanf,printf and send to Visual C++ 2010 B-). For some reason other combinations don't work.

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

    Thanks, it passed. I don't understand why it was giving me WA. I hate this judges

    → Reply