Calculating the number of graphs created and the number of vertices in each graph from a list of edges

Question

Given a list of edges such as, edges = [[1,2],[2,3],[3,1],[4,5]]

I need to find how many graphs are created, by this I mean how many groups of components are created by these edges. Then get the number of vertices in the group of components.

However, I am required to be able to handle 10^5 edges, and i am currently having trouble completing the task for large number of edges.

My algorithm is currently getting the list of edges= [[1,2],[2,3],[3,1],[4,5]] and merging each list as set if they have a intersection, this will output a new list that now contains group components such as , graphs = [[1,2,3],[4,5]]

There are two connected components : [1,2,3] are connected and [4,5] are connected as well.

I would like to know if there is a much better way of doing this task.

def mergeList(edges):
    sets = [set(x) for x in edges if x]
    m = 1
    while m:
        m = 0
        res = []
        while sets:
            common, r = sets[0], sets[1:]
            sets = []
            for x in r:
                if x.isdisjoint(common):
                    sets.append(x)
                else:
                    m = 1
                    common |= x
            res.append(common)
        sets = res
    return sets

I would like to try doing this in a dictionary or something efficient, because this is toooo slow.

Answer 1

A basic iterative graph traversal in Python isn't too bad.

import collections


def connected_components(edges):
    # build the graph
    neighbors = collections.defaultdict(set)
    for u, v in edges:
        neighbors[u].add(v)
        neighbors[v].add(u)
    # traverse the graph
    sizes = []
    visited = set()
    for u in neighbors.keys():
        if u in visited:
            continue
        # visit the component that includes u
        size = 0
        agenda = {u}
        while agenda:
            v = agenda.pop()
            visited.add(v)
            size += 1
            agenda.update(neighbors[v] - visited)
        sizes.append(size)
    return sizes