Избыточное ребро и обнаружение циклов

Что такое избыточное ребро

# Example
# n=5, edges = [[1,2],[1,3],[2,3],[2,4],[3,5]]
# Adding edge [2,3] creates cycle 1-2-3-1
# So [2,3] is the redundant connection

# Key insight: process edges one by one with DSU
# The FIRST edge where both endpoints are already connected is the redundant one
print('Tree property: n nodes, n-1 edges, no cycles')
print('Adding 1 edge: n nodes, n edges, exactly 1 cycle')
print('DSU approach: find the edge that connects already-connected nodes')

Обнаружение циклов с помощью DSU

def find_redundant_connection(edges):
    n = len(edges)
    parent = list(range(n + 1))  # 1-indexed
    rank = [0] * (n + 1)

    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]

    def union(x, y):
        px, py = find(x), find(y)
        if px == py:
            return False           # same component => cycle found
        if rank[px] < rank[py]: px, py = py, px
        parent[py] = px
        if rank[px] == rank[py]: rank[px] += 1
        return True

    for u, v in edges:
        if not union(u, v):
            return [u, v]     # this edge creates the cycle

edges = [[1,2],[1,3],[2,3],[2,4],[3,5]]
print(find_redundant_connection(edges))  # [2, 3]

Пошаговый разбор алгоритма

def find_redundant_trace(edges):
    parent = list(range(len(edges) + 1))

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    for u, v in edges:
        pu, pv = find(u), find(v)
        print(f'Edge ({u},{v}): find({u})={pu}, find({v})={pv}', end=' => ')
        if pu == pv:
            print('CYCLE DETECTED!')
            return [u, v]
        parent[pv] = pu
        print('merged')
    return []

result = find_redundant_trace([[1,2],[1,3],[2,3]])
print('Redundant edge:', result)

Обнаружение циклов в неориентированных графах с помощью DFS

from collections import defaultdict

def has_cycle_dfs(n, edges):
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)

    visited = set()

    def dfs(node, parent):
        visited.add(node)
        for nb in graph[node]:
            if nb == parent:
                continue           # skip the edge we came from
            if nb in visited:
                return True        # back edge => cycle
            if dfs(nb, node):
                return True
        return False

    for node in range(1, n + 1):
        if node not in visited:
            if dfs(node, -1):
                return True
    return False

print(has_cycle_dfs(3, [[1,2],[1,3],[2,3]]))  # True
print(has_cycle_dfs(3, [[1,2],[1,3]]))        # False

Обнаружение циклов в ориентированных графах

def has_cycle_directed(n, edges):
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)

    # 0=white(unvisited), 1=grey(in stack), 2=black(done)
    color = [0] * (n + 1)

    def dfs(node):
        color[node] = 1            # grey: currently visiting
        for nb in graph[node]:
            if color[nb] == 1:
                return True        # back edge to grey node => cycle
            if color[nb] == 0:
                if dfs(nb):
                    return True
        color[node] = 2            # black: fully processed
        return False

    for node in range(1, n + 1):
        if color[node] == 0:
            if dfs(node):
                return True
    return False

from collections import defaultdict
print(has_cycle_directed(3, [[1,2],[2,3],[3,1]]))  # True: 1->2->3->1
print(has_cycle_directed(3, [[1,2],[1,3],[2,3]]))  # False

Избыточное соединение II: вариант для ориентированных графов

def find_redundant_directed(edges):
    n = len(edges)
    parent_map = {}          # node -> its parent in the input
    candidate1 = candidate2 = None

    for u, v in edges:
        if v in parent_map:                # v already has a parent
            candidate1 = [parent_map[v], v]  # earlier edge
            candidate2 = [u, v]              # later edge
        else:
            parent_map[v] = u

    # DSU cycle detection, skipping candidate2 if it exists
    dsu = list(range(n + 1))
    def find(x):
        while dsu[x] != x: dsu[x] = dsu[dsu[x]]; x = dsu[x]
        return x
    def union(x, y):
        px, py = find(x), find(y)
        if px == py: return False
        dsu[px] = py; return True

    for u, v in edges:
        if candidate2 and [u, v] == candidate2: continue   # skip candidate2
        if not union(u, v):              # cycle found without candidate2
            return candidate1 if candidate1 else [u, v]

    return candidate2   # no cycle when excluding candidate2 => candidate2 is redundant

print(find_redundant_directed([[1,2],[1,3],[2,3]]))  # [2,3]
print(find_redundant_directed([[1,2],[2,3],[3,4],[4,1],[1,5]]))  # [4,1]

Проверка корректности графа после удаления ребра

def verify_tree(n, edges, removed_edge):
    parent = list(range(n + 1))

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    components = n
    for u, v in edges:
        if [u, v] == removed_edge:
            continue         # skip the removed edge
        pu, pv = find(u), find(v)
        if pu == pv:
            print('CYCLE DETECTED after removal! Wrong answer.')
            return False
        parent[pv] = pu
        components -= 1

    if components != 1:
        print(f'Graph not connected ({components} components). Wrong answer.')
        return False
    print('Valid tree after removing edge:', removed_edge)
    return True

edges = [[1,2],[1,3],[2,3]]
verify_tree(3, edges, [2,3])
verify_tree(3, edges, [1,2])  # wrong removal

Анализ временной и пространственной сложности

# Summary of complexities
complexity = {
    'Naive (DFS after each edge)': {'time': 'O(n^2)', 'space': 'O(n)'},
    'DSU (path compression + rank)': {'time': 'O(n * alpha(n))', 'space': 'O(n)'},
    'Sorting + DSU (Kruskal style)': {'time': 'O(n log n)', 'space': 'O(n)'},
}
for approach, costs in complexity.items():
    print(f'{approach}:')
    print(f'  Time:  {costs["time"]}')
    print(f'  Space: {costs["space"]}')
    print()
print('alpha(n) <= 4 for all practical n, so DSU is effectively O(n).')

Граничный случай: петля

def find_redundant_robust(edges):
    n = len(edges)
    parent = list(range(n + 1))

    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]

    for u, v in edges:
        pu, pv = find(u), find(v)
        if pu == pv:
            return [u, v]   # handles self-loops too: u==v => pu==pv always
        parent[pv] = pu
    return []

# Self-loop test
print(find_redundant_robust([[1,2],[2,2]]))    # [2,2] self-loop
# Minimum tree test
print(find_redundant_robust([[1,2],[2,3],[1,3]]))  # [1,3]
# Standard test
print(find_redundant_robust([[1,2],[1,3],[2,3],[2,4],[3,5]]))  # [2,3]

Обобщение обнаружения циклов для разных алгоритмов

# When to use which cycle-detection method:
# Problem type => preferred algorithm

problems = [
    ('Redundant Connection (undirected)', 'DSU'),
    ('Course Schedule (directed)', 'DFS three-color or Kahn topological sort'),
    ('Detect cycle in undirected graph', 'DFS with parent tracking or DSU'),
    ('Find cycle members in directed graph', 'DFS three-color + backtrack'),
    ('Online graph edges with cycle check', 'DSU'),
    ('Minimum spanning tree validity', 'DSU (Kruskal)'),
]
for problem, solution in problems:
    print(f'{problem}\n  => {solution}\n')

Полное решение с учётом граничных случаев

def find_redundant_connection(edges):
    n = len(edges)
    parent = list(range(n + 1))
    rank = [0] * (n + 1)

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]   # path halving
            x = parent[x]
        return x

    def union(x, y):
        px, py = find(x), find(y)
        if px == py:
            return False
        if rank[px] < rank[py]:
            px, py = py, px
        parent[py] = px
        if rank[px] == rank[py]:
            rank[px] += 1
        return True

    for u, v in edges:
        if not union(u, v):
            return [u, v]
    return []  # should never reach here given valid input

test_cases = [
    [[1,2],[1,3],[2,3]],
    [[1,2],[2,3],[3,4],[1,4],[1,5]],
    [[1,2],[1,3],[2,3],[2,4],[3,5]],
]
for tc in test_cases:
    print(find_redundant_connection(tc))

Быстрая проверка

Итоги урока