Problem p03108 (python)

Fixed submission:
N, M = map(int, input().split())
AB = []

for _ in range(M):
    a, b = map(int, input().split())
    AB.append((a-1, b-1))

class UnionFind():
    def __init__(self, n):
        # negative if parent
        # if parent, absolute value represents the number of nodes in the union
        # if child, value represents the parent node to it
        self.parent = [-1 for _ in range(n)]
        
    def root(self, x):
        if self.parent[x] < 0:
            return x

        else:
            # recursively trace a parent node until it gets to a root while updating every node so that they are directly connected to their common parent
            self.parent[x] = self.root(self.parent[x])
            return self.parent[x]

    def size(self, x):
        return -1 * self.parent[self.root(x)]
    
    def union(self, x, y):
        x = self.root(x)
        y = self.root(y)

        if x == y:
            return False

        else:
            size_x = - self.size(x) 
            size_y = - self.size(y)

            # make sure y is shorter so that always shorter tree(y) is atached to longer tree(x) 
            if size_x > size_y:
                x, y = y, x 

            self.parent[x] += self.parent[y]
            self.parent[y] = x

            return size_x, size_y


n_solo = N * (N - 1) // 2 
ans = [n_solo]
uf = UnionFind(N)

for a, b in reversed(AB):

    united = uf.union(uf.root(a), uf.root(b))

    if united:
        n_solo -= united[0] * united[1]

    ans.append(n_solo)
    
for a in reversed(ans[:-1]):
    print(a)

Buggy submission (verdict: Runtime Error):
#%%
class Island:
    def __init__(self,key):
        self.id = key
        self.connectedTo = set()

    def addNeighbor(self,nbr):
        self.connectedTo.add(nbr)

    def getConnections(self):
        return self.connectedTo.keys()

    def getId(self):
        return self.id

class Graph:
    def __init__(self):
        self.islandList = {}
        self.bridgeList = []
        self.numIslands = 0

    def addIsland(self,key):
        self.numIslands += 1
        newIsland = Island(key)
        self.islandList[key] = newIsland
        return newIsland

    def getIsland(self,key):
        if key in self.islandList:
            return self.islandList[key]
        else:
            return None

    def __contains__(self,n):
        return n in self.islandList

    def addBridge(self,f,t):
        if f not in self.islandList:
            nv = self.addIsland(f)
        if t not in self.islandList:
            nv = self.addIsland(t)
        self.islandList[f].addNeighbor(self.islandList[t])
        self.islandList[t].addNeighbor(self.islandList[f])
        self.bridgeList.insert(0,(f,t))

    def removeBrige(self):
        f,t = self.bridgeList.pop()
        self.islandList[f].connectedTo.remove(t)
        self.islandList[t].connectedTo.remove(f)
        return (f,t)

    def getIslands(self):
        return self.islandList.keys()

    def __iter__(self):
        return iter(self.islandList.values())

#%%
def findPath(start, dest):

    visited = set()

    flag = search(world.islandList[start].getConnections(), visited)

    return flag

def search(iterable, visited):
    pass

#%%
n,m = map(int, input().split())

world = Graph()

for i in range(i,n+1):
    world.addIsland(i)

for _ in range(m):
    world.addBridge(map(int, input().split()))

while world.bridgeList():
    
    world.removeBrige()

    ans = 0

    for start in world.islandList():
        for dest in world.islandList():
            if not start == dest:
                flag = findPath(start,dest)

                if not flag:
                    ans += 1

    print(ans)