Количество компонент связности в графе

Question

Дан неориентированный невзвешенный граф, состоящий из N вершин и M ребер. Необходимо посчитать количество его компонент связности и вывести их.

Формат ввода

Во входном файле записано два числа N и M (0 < N ≤ 100000, 0 ≤ M ≤ 100000). В следующих M строках записаны по два числа i и j (1 ≤ i, j ≤ N), которые означают, что вершины i и j соединены ребром.

Формат вывода

В первой строчке выходного файла выведите количество компонент связности. Далее выведите сами компоненты связности в следующем формате: в первой строке количество вершин в компоненте, во второй - сами вершины в произвольном порядке.

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

dicter = {i: [] for i in range(1, n + 1)}

for i in range(m):
    f, s = map(int, input().split())
    dicter[f] += [s]
    dicter[s] += [f]

done = set()


def req(dicter, curr, done):
    done.add(curr)
    for p in dicter[curr]:
        if p not in done:
            req(dicter, p, done)


new_done = set()
lister = set()

for key in dicter.keys():
    if key not in done and key not in new_done:
        req(dicter, key, done)
        lister.add(tuple(sorted(done)))
        new_done.union(done)
        done.clear()


print(len(lister))

for l in lister:
    print(len(l))
    print(*l)

Вроде работает, но ловлю runtime error на одном из тестов (что это за тест не знаю). Где тут его можно словить вообще? Уже вторая задача на графы и получаю рантайм походу на том же самом тесте...

Немного изменил, теперь этот тест прошел, но на следующем рантайм...

n, m = map(int, input().split())
from collections import deque

dicter = {i: [] for i in range(1, n + 1)}

for i in range(m):
    f, s = map(int, input().split())
    dicter[f] += [s]
    dicter[s] += [f]

visited = [False] * (n + 1)


def req(dicter, visited, curr, ret):
    visited[curr] = True
    ret.append(curr)
    for p in dicter[curr]:
        if not visited[p]:
            req(dicter, visited, p, ret)


new_done = set()
lister = []

for key in dicter.keys():
    ret = []
    if not visited[key]:
        req(dicter, visited, key, ret)
        lister.append(ret)
        new_done = new_done | set(ret)

print(len(lister))

for l in lister:
    print(len(l))
    print(*l)

Окей, увеличил глубину рекурсии(причем довольно сильно), рантайм пропал, теперь просто слишком долго...)

Answer 1

Структура графа здесь особо не нужна, поэтому можно воспользоваться структурой данных "система непересекающихся множеств" (union-find)

from collections import defaultdict

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

parent = [i for i in range(n+1)]
rank = [0] * (n+1)

def dsu_find(x):
    return x if parent[x]==x  else dsu_find(parent[x])

def dsu_join(a, b):
    a = dsu_find(a)
    b = dsu_find(b)
    if a != b:
        if rank[a] < rank[b]:
            a, b = b, a
        parent[b] = a
        if rank[a] == rank[b]:
            rank[a] += 1

for i in range(m):
    a, b = map(int, input().split())
    dsu_join(a, b)

dd = defaultdict(list)
for i in range(1, n+1):
    dd[dsu_find(i)].append(i)

print(len(dd))
for v in dd.values():
    print(*v)

Answer 2

Вот это решение прошло. Все из-за того, что я не обновлял множество, а по сути каждый раз делал новое.

import sys
sys.setrecursionlimit(150000)

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

adj_list = {i: [] for i in range(1, n + 1)}

for _ in range(m):
    f, s = map(int, input().split())
    adj_list[f] += [s]
    adj_list[s] += [f]

visited_nodes = [False] * (n + 1)
viset = set()


def req(dicter, visited, curr, ret):
    visited[curr] = True
    ret.append(curr)
    for p in dicter[curr]:
        if not visited[p]:
            req(dicter, visited, p, ret)


lister = []

for key in adj_list.keys():
    if not visited_nodes[key]:
        ret = []
        req(adj_list, visited_nodes, key, ret)
        lister.append(ret)
        viset.update(ret)

print(len(lister))

for l in lister:
    print(len(l))
    print(*l)

БЛОГ НА HUSL

Количество компонент связности в графе

Ответы (2 шт):