Graphs (Union Find): 684. Redundant Connection

684. Redundant Connection

 

https://youtu.be/1lNK80tOTfc

 

 

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. 입력 순서 보장:
   • 간선은 순차적으로 처리되므로, 마지막으로 처리된 간선이 우선순위를 가짐.

최종 코드

🔍 문제 요약

• 입력: 트리 형태로 주어진 그래프에 간선 하나가 추가됨 (그래서 사이클이 생김)
• 목표: 이 때 사이클을 만들게 되는 간선을 찾아 반환

class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        # 노드 개수만큼 parent 초기화 (1-based)
        par = [i for i in range(len(edges)+1)]
        rank = [1] * (len(edges)+1)  # 각 노드의 트리 크기 (초기 1)

        # 루트 노드를 찾는 함수 (Path Compression 포함)
        def findRoot(n):
            p = par[n]

            # 루트가 아닐 경우 계속 위로 올라감
            while p != par[p]:
                par[n] = par[par[p]]  # 경로 압축: 조상의 조상으로 건너뜀
                p = par[p]  # 위로 계속 탐색
            return p  # 루트 반환

        # Union 함수: 두 노드의 루트를 합침
        def union(n1, n2):
            p1, p2 = findRoot(n1), findRoot(n2)

            if p1 == p2:
                # 두 노드의 루트가 같다면, 이미 연결된 상태 → 사이클 발생
                return False

            # rank가 더 큰 쪽이 부모가 됨
            if rank[p1] > rank[p2]:
                par[p2] = p1
                rank[p1] += rank[p2]
            else:
                par[p1] = p2
                rank[p2] += rank[p1]
            return True

        # 모든 간선을 순회하며 Union 수행
        for e1, e2 in edges:
            if not union(e1, e2):  # 사이클이 생기는 간선이면
                return [e1, e2]    # 해당 간선을 반환 (Redundant edge)