Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

vkditya0997's blog

By vkditya0997, history, 5 years ago, ,

I solved this by a brute force
By removing each and every pair, if no of connected components are greater than initial no , count ++
But it was very lengthy, and I saw many short codes, Which I couldn't understand?
Any optimized Algorithm to solve these kind of problems?
 » 5 years ago, # | ← Rev. 3 →   0 The main point here is not to use an optimized algorithm. Instead, use the simplest algorithm that is fast enough.With n=20, you can use Floyd-Warshall and two cycles to count connected components in like 5 lines of code. Here is my code that does that: from copy import deepcopy def countComponents(G, f1=-1, f2=-1): # gets a graph G; optionally, gets two forbidden vertices f1 and f2 # counts connected components N = len(G) G = deepcopy(G) # make a copy of G that can be modified locally vertices = [ x for x in range(N) if x!=f1 and x!=f2 ] for k in vertices: for i in vertices: for j in vertices: G[i][j] = G[i][j] or (G[i][k] and G[k][j]) return sum( all(not G[j][i] for j in vertices if j base for a in range(len(G)) for b in range(a) )