vkditya0997's blog

By vkditya0997, history, 8 years ago, In English

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?
Thanks in advance !

  • Vote: I like it
  • -6
  • Vote: I do not like it

| Write comment?
»
8 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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<i) for i in vertices )

class Fragile2:
    def countPairs(self, G):
        G = [ [ c=='Y' for c in row ] for row in G ]
        base = countComponents(G)
        return sum( countComponents(G,a,b) > base for a in range(len(G)) for b in range(a) )