Graphs (Union Find): 684. Redundant Connection

684. Redundant Connection

 

https://youtu.be/FXWRE67PLL0?si=09q1EDMfBhbMNpJk

 

class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        # Union-Find 알고리즘으로 사이클을 형성하는 간선을 찾는 함수
        # Use Union-Find algorithm to find the edge that creates a cycle.

        n = len(edges)  # 간선의 개수 (Number of edges)
        
        # 부모 노드를 저장하는 배열 (Parent array to store parent of each node)
        par = [i for i in range(n+1)]  # 초기에는 각 노드가 자기 자신을 부모로 가짐 (Initially, each node is its own parent)
        
        # 랭크 배열 (Rank array to store the height of each tree)
        rank = [1] * (n+1)  # 각 노드의 랭크를 1로 초기화 (Initialize rank as 1 for all nodes)

        # 부모(루트 노드)를 찾는 함수 (Find function to locate the root parent)
        def find(node):
            res = node  # 현재 노드에서 시작 (Start with the current node)

            # 루트 노드를 찾을 때까지 반복 (Keep moving up until the root is found)
            while res != par[res]:
                par[res] = par[par[res]]  # 경로 압축 (Path compression to make the parent point to the root)
                res = par[res]  # 부모 노드로 이동 (Move to the parent)
            return res  # 루트 부모 반환 (Return the root parent)

        # 두 노드를 같은 그룹으로 합치는 함수 (Union function to merge two nodes into the same group)
        def union(n1, n2):
            # 두 노드의 루트 부모를 찾음 (Find root parents of both nodes)
            p1, p2 = find(n1), find(n2)

            # 두 노드가 이미 같은 그룹에 속하면 사이클이 형성됨 (If they are already in the same group, a cycle is formed)
            if p1 == p2:
                return 0

            # 랭크 기반으로 트리를 합침 (Union by rank to keep the tree balanced)
            if rank[p1] > rank[p2]:  # p1의 트리가 더 높으면 (If p1's tree is taller)
                par[p2] = p1  # p2의 부모를 p1로 설정 (Make p1 the parent of p2)
                rank[p1] += rank[p2]  # p1의 랭크를 갱신 (Update the rank of p1)
            else:  # p2의 트리가 더 높거나 같으면 (If p2's tree is taller or equal)
                par[p1] = p2  # p1의 부모를 p2로 설정 (Make p2 the parent of p1)
                rank[p2] += rank[p1]  # p2의 랭크를 갱신 (Update the rank of p2)
            return 1  # 그룹이 합쳐졌음을 나타냄 (Indicate that a union occurred)

        # 간선을 순회하며 Union-Find 연산 수행 (Iterate through edges and perform Union-Find operations)
        for n1, n2 in edges:
            # 만약 두 노드가 같은 그룹에 속해 있다면 해당 간선 반환 (If the two nodes are in the same group, return the edge)
            if union(n1, n2) == 0:
                return [n1, n2]  # 사이클을 형성한 간선을 반환 (Return the edge that forms a cycle)

 

문제 분석 및 해석

문제 설명

• 트리의 정의:
  • 무방향 그래프.
  • 모든 노드가 연결되어 있으며, 사이클이 없음.
• 주어진 조건:
  • 그래프는 nnn개의 노드로 구성된 트리에서 시작.
  • 여기에 하나의 간선이 추가되어 사이클이 생김.
  • edges[i]=[ai,bi] 는 ai 와 bi 사이에 간선이 존재함을 의미.
• 목표:
  • 하나의 간선을 제거하여 사이클을 없애고, 그래프를 다시 트리로 만듦.
  • 여러 답이 있을 경우, 입력에서 가장 마지막에 나타난 간선을 반환.

---

해결 방법: Union-Find (Disjoint Set Union, DSU)

Union-Find는 노드 간 연결 상태를 추적하고, 사이클을 탐지하는 데 적합한 알고리즘입니다.

알고리즘 단계

1. 초기화:
   • 각 노드는 자신을 부모로 가짐.
   • rank 배열로 트리의 높이를 관리.
2. 간선 순회:
   • 각 간선을 추가하며 두 노드가 이미 같은 그룹에 속하는지 확인.
   • 같은 그룹에 속한다면, 해당 간선이 사이클을 형성하는 간선.
3. 사이클 탐지:
   • 간선 추가 시 두 노드가 이미 같은 루트를 공유한다면, 해당 간선을 반환.
4. 입력 순서 보장:
   • 간선은 순차적으로 처리되므로, 마지막으로 처리된 간선이 우선순위를 가짐.