Maximum SCC size in a directed graph if one new edge can be added.

Revision en1, by r3novatio, 2020-10-26 22:49:59

I came across this problem in which you have been given a directed graph $$$G=(V,E)$$$ with $$$|V|,|E|\leq 10^5$$$ and one additional edge can be added to $$$E$$$. What can be the maximum size of a strongly connected component in the resulting graph?

Best I could think of was an $$$O(V(V+E))$$$ approach. If anyone knows any better running time algorithm, do share your approach.

Thanks.

Tags #graphs, #graph theory, directed graph, strongly connected, #scc

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English r3novatio 2020-10-27 10:07:27 189
en1 English r3novatio 2020-10-26 22:49:59 444 Initial revision (published)