Count edges in directed graph considering if (a,b) & (b,c) are 2 edges => edge (c,a) can be added

Revision en1, by elizabeth_zou_fanboi, 2024-11-12 00:37:00

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

Tags directed graph, counting

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English elizabeth_zou_fanboi 2024-11-12 00:37:00 523 Initial revision (published)