def sp3(G):
    nodes = list(G.nodes)
    P = []
    dic = {}
    for v in nodes:
        dic[v] = frozenset([v])
    for v in nodes:
        nb = random.choice(list(G.neighbors(v)))
        U = frozenset.union(dic[v],dic[nb])
        for a in U:
            dic[a] = U
    for v in nodes:
        P.append(dic[v])
    P = list(set(P))
    return P

def sp1(G):
    nodes = list(G.nodes)
    dic = {v:set() for v in nodes}
    for v in nodes:
        nb = random.choice(list(G.neighbors(v)))
        dic[v].add(nb)
        dic[nb].add(v)
    P = list(CCbfs(dic))
    return P

def CCbfs(dic):
    seen = set()
    for v in dic.keys():
        if v not in seen:
            c = frozenset(bfs(dic, v))
            yield c
            seen.update(c)

def bfs(dic,n):
    d = dic
    seen = set()
    nextlevel = {n}
    while nextlevel:
        thislevel = nextlevel
        nextlevel = set()
        for v in thislevel:
            if v not in seen:
                yield v
                seen.add(v)
                nextlevel.update(d[v])