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

Revision en2, by r3novatio, 2020-10-27 10:07:27

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?

If anyone knows an approach, do share.

Thanks.

EDIT: I apologize that the $O(V.(V+E))$ algorithm that I thought would solve this also turned out to be incorrect.

#### History

Revisions

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