1

Мой код прошел не все тесты(( а что не так? вот задача https://informatics.msk.ru/mod/statements/view.php?id=256&chapterid=111540#1

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

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

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

def am(now):
    visited.append(now)
    new_visited.append(now)
    for i in range(1, n+1):
        if i not in visited and i in graph[now]:
            am(i)
    
n,m = map(int, input().split())
graph = [0] * (n+1)
for i in range(n+1):
    graph[i] = []
for i in range(m):
    k,w = map(int, input().split())
    graph[k].append(w)
    graph[w].append(k)
visited = []
new_visited = []
new_new_visited = []
while len(visited) != n:
    for i in range(1, n+1):
        if i not in visited:
            am(i)
            break
    new_new_visited.append(new_visited)
    new_visited = []
print(len(new_new_visited))
for i in new_new_visited:
    print(len(i))
    print(*i)
3
  • Проблема в компиляторе
    – user256707
    24 июл в 19:50
  • в смысле? Какие-то тесты прошел, какие-то нет 24 июл в 20:45
  • какое замечательное предложение, я согласна))) 24 июл в 21:55

1 ответ 1

2

Проблемы

  1. i not in visited выполяются медленно, за линейное время, так как visited - список. Замена на множество ускоряет алгоритм в N раз.

  2. Вот этот цикл делает N итераций:

        for i in range(1, n+1):
            if i not in visited and i in graph[now]:
                am(i)
    

    А этот выполняет ту же работу за len(graph[now]) итераций:

        for i in graph[now]:
            if i not in visited:
                am(i)
    

    Ещё одно ускорение в N раз.

  3. Цикл for начинает поиск с начала графа для каждой новой компоненты связности - сложность NK для K компонент:

    while len(visited) != n:
        for i in range(1, n+1):
            if i not in visited:
                am(i)
                break
        new_new_visited.append(new_visited)
        new_visited = []
    

    А этот цикл всю работу делает за время N вне зависимости от K:

    for i in range(1, n+1):
        if i not in visited:
            am(i)
            new_new_visited.append(new_visited)
            new_visited = []
    

    В худшем случае K = N - ускорение в N раз.

  4. Функция am рекурсивна. Глубина рекурсии в Питоне обычно тысяча вызовов, иногда две или три тысячи. Если в графе найдется цикл длиной десять тысяч, глубины рекурсии не хватит. Шестнадцатый тест упадет.

    Функцию можно переписать без рекурсии, на стеке:

    def am(start):
        visited.add(start)
        stack = [start]
        while stack:
            now = stack.pop()
            new_visited.append(now)
            for i in graph[now]:
                if i not in visited:
                    visited.add(i)
                    stack.append(i)
    

Код

Ваш код с четырьмя изменениями проходит все тесты:

def am(start):
    visited.add(start)
    stack = [start]
    while stack:
        now = stack.pop()
        new_visited.append(now)
        for i in graph[now]:
            if i not in visited:
                visited.add(i)
                stack.append(i)

    
n, m = map(int, input().split())
graph = [0] * (n+1)
for i in range(n+1):
    graph[i] = []
for i in range(m):
    k, w = map(int, input().split())
    graph[k].append(w)
    graph[w].append(k)

visited = set()
new_visited = []
new_new_visited = []

for i in range(1, n+1):
    if i not in visited:
        am(i)
        new_new_visited.append(new_visited)
        new_visited = []

print(len(new_new_visited))
for i in new_new_visited:
    print(len(i))
    print(*i)

Ещё код

Нет глобальных переменных, генераторы вместо списков - xотя это дело вкуса. visited не обязан быть множеством, список булевых флагов тоже работает:

def components(graph):
    visited = [False] * len(graph)

    def traverse(i):
        visited[i] = True
        stack = [i]
        while stack:
            i = stack.pop()
            yield i
            for j in graph[i]:
                if not visited[j]:
                    visited[j] = True
                    stack.append(j)

    for i in range(1, len(graph)):
        if not visited[i]:
            yield tuple(traverse(i))


def main():
    n, m = map(int, input().split())
    graph = tuple([] for _ in range(n + 1))
    for _ in range(m):
        i, j = map(int, input().split())
        graph[i].append(j)
        graph[j].append(i)

    answer = tuple(components(graph))

    print(len(answer))
    for c in answer:
        print(len(c))
        print(*c)


main()

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.