Bridges. Мосты

Шешімді жөнелту
Ұпайлар: 1
Уақыт шектеуі: 2.0s
Жад шектеуі: 64M
Author:
zharaskhan
Problem type
Рұқсат етілген тілдер
Assembly, Awk, Brain****, C, C++, Java, Pascal, Perl, Python, Sed, Text

Дан неориентированный граф. Требуется найти все мосты в нем.

Входные данные

Первая строка входного файла содержит два натуральных числа \(n\) и \(m\) — количества вершин и ребер графа соответственно (\(n \leqslant 20\,000\), \(m \leqslant 200\,000\)).

Следующие \(m\) строк содержат описание ребер по одному на строке. Ребро номер \(i\) описывается двумя натуральными числами \(b_i\), \(e_i\) — номерами концов ребра (\(1 \leqslant b_i, e_i \leqslant n\)).

Выходные данные

Первая строка выходного файла должна содержать одно натуральное число \(b\) — количество мостов в заданном графе. На следующей строке выведите \(b\) целых чисел — номера ребер, которые являются мостами, в возрастающем порядке. Ребра нумеруются с единицы в том порядке, в котором они заданы во входном файле.

Примеры

Ввод 1
10 16
5 7
2 8
6 1
6 4
1 2
2 10
4 8
3 9
10 8
9 5
10 4
6 8
1 4
3 7
10 3
6 2
Ответ 1
1
15

Пікірлер


  • 0
    baurzhan16  пікір қалдырды Қар. 28, 2025, 6:35 Т.Ж.

    import sys sys.setrecursionlimit(10**7)

    n, m = map(int, sys.stdin.readline().split())

    Граф adjacency list ретінде (u → (v, edge_id))

    g = [[] for _ in range(n + 1)] edges = []

    for i in range(1, m + 1): u, v = map(int, sys.stdin.readline().split()) edges.append((u, v)) g[u].append((v, i)) g[v].append((u, i))

    tin = [0] (n + 1) low = [0] (n + 1) visited = [False] * (n + 1) timer = 1 bridges = []

    def dfs(v, parent_edge): global timer visited[v] = True tin[v] = low[v] = timer timer += 1

    for to, eid in g[v]:
    if eid == parent_edge:
        continue

    if visited[to]:
        # Back edge
        low[v] = min(low[v], tin[to])
    else:
        dfs(to, eid)
        low[v] = min(low[v], low[to])

        # Bridge condition
        if low[to] > tin[v]:
            bridges.append(eid)

    Граф байланыссыз болуы мүмкін → барлық компоненттен іздейміз

    for v in range(1, n + 1): if not visited[v]: dfs(v, -1)

    Нәтижені сұрыптаймыз

    bridges.sort()

    Шығару

    print(len(bridges)) if bridges: print(*bridges)