Submission #62540348

---

Source Code Expand

class DisjointSet():

    def __init__(self,size : int) -> None:
        self.parent = [i for i in range(size)] # Sets parent of every node to itself
        self.rank = [0 for _ in range(size)] # Sets the size of every set to 1

    def find_set(self,v : int) -> int:

        if (self.parent[v] == v): return v

        # Finds parents highest ancestor
        parent = self.find_set(self.parent[v])

        # Set current parent to highest ancestor
        self.parent[v] = parent

        return parent
    
    def union(self,v : int, u : int) -> None:
        
        # Find high parents of both nodes
        a = self.find_set(v)
        b = self.find_set(u)

        if a == b: return

        # Connects smaller tree to bigger tree
        if (self.rank[a] > self.rank[b] ): a,b = b,a
        self.parent[a] = b
        
        # Incrases rank if both trees have same rank.
        if (self.rank[b] == self.rank[a]): self.rank[b] += 1

n,m = map(int,input().split())
dsu = DisjointSet(n+1)
redundant = []

for i in range(m):
    a,b = map(int,input().split())
    if dsu.find_set(a) == dsu.find_set(b):
        redundant.append((i+1,a,b))
    else:
        dsu.union(a,b)



seen = set()
for i in range(1,n+1):
    seen.add(dsu.find_set(i))

res = []

for edge in redundant:
    i, x, y = edge

    par_i = dsu.find_set(x)
    for j in seen:
        if par_i != dsu.find_set(j):
            res.append((i,x,j))
            seen.remove(j)
            dsu.union(x,j)
            break
        
    if len(seen) == 1:
        break
    
print(len(res))
for i in res:
    print(' '.join([*map(str,i)]))

Submission Info

Judge Result