0
$\begingroup$

This question already has an answer here:

I have a connected undirected graph with V vertices and V(V - 1)/2 edges. Then, I remove K edges (a[i], b[i]). I want to know if the graph is still connected after performing all the operations (so I want to delete those edges and then answer the question). Is there any faster way to do this than performing BFS/DFS algorithm? Those are linear time algorithms but in terms of edges which may be quite big to compute on a home PC for graphs with approximately 10^6 vertices. K of course will not be too big, let's say 10^6.

$\endgroup$

merged by D.W. Oct 11 '16 at 15:13

This question was merged with Deleting edges from complete graph because it is an exact duplicate of that question.

Browse other questions tagged or ask your own question.