We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Friend Circle Queries
  2. Discussions

Friend Circle Queries

  • amourayuba
     + 0 comments

    My Disjoint Set solution. Just a small modification to a dictionnary for the size and parents instead of an array.

    # ACUTAL SOLUTION WITH DISJOINT SET 
class DisjointSet:
    def __init__(self):
        self.parent = {}
        self.size = {}

    def find(self, i):
        if i not in self.parent:
            self.parent[i] = i
            self.size[i] = 1
            return i
        if self.parent[i] != i:
            self.parent[i] = self.find(self.parent[i])
        return self.parent[i]

    def unionBySize(self, i, j):
        irep = self.find(i)
        jrep = self.find(j)
        if irep == jrep:
            return
        isize = self.size[irep]
        jsize = self.size[jrep]

        if isize < jsize:
            self.parent[irep] = jrep
            self.size[jrep] += self.size[irep]
        else:
            self.parent[jrep] = irep
            self.size[irep] += self.size[jrep]


def maxCircle(queries):
    dset = DisjointSet()
    maxlen = 0
    maxlens = []
    for query in queries:
        f1, f2 = query
        dset.unionBySize(f1, f2)
        maxlen = max(maxlen, dset.size[dset.find(f1)])
        maxlens.append(maxlen)
    return maxlens