elizabeth_zou_fanboi's blog

Count edges in directed graph considering if (a,b) & (b,c) are 2 edges => edge (c,a) can be added
By elizabeth_zou_fanboi, history, 6 weeks ago, In English

You are given a directed graph of N nodes. Initially there are M directed edges which are given as input (these are unique and self edges are allowed). You can add a new edge (c, a) if the edges (a,b) and (b,c) exist in the graph. Find the total no of edges in the final graph (when you cannot add any more edges)

NOTE: (a,b) & (b,c) => (c,a) and NOT (a,c)

Constraint: N = 100,000, M = 100,000, TimeLimit = 2s

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

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I am reposting this blog as I accidentally deleted the old blog with the same problem (I thought I was discarding the edit and deleted it)

→ Reply
»
6 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

problem

solution

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

    thanks for finding this. Did you find this problem from the memory of seeing this in a previous contest ? ( I am curious how did you find the exact contest even if you remembered that you saw/solved this problem in an earlier contest )

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

    agc F 💀

    → Reply