What is the best way to solve Redundant Connection?

The optimized O(n) approach using Graphs patterns is generally preferred.

상위 150개 인터뷰쉬움

중복 연결

'중복 연결' 문제에 대한 자세한 가이드 및 Python 구현입니다.

문제 설명

쉬움

이 문제에서 트리는 순환이 없고 연결되어 있는 무방향 그래프입니다.

1부터 n까지 레이블이 지정된 n개의 노드가 있고 하나의 추가 간선이 추가된 트리로 시작된 그래프가 제공됩니다. 추가된 Edge는 1부터 n까지 선택된 서로 다른 두 개의 정점을 가지며, 이미 존재하는 Edge가 아닙니다. 그래프는 길이 n의 배열 가장자리로 표시됩니다. 여기서 edge[i] = [ai, bi]는 노드 ai와 bi 사이에 방향이 지정되지 않은 가장자리가 있음을 나타냅니다.

결과 그래프가 n 노드의 트리가 되도록 제거할 수 있는 간선을 반환합니다. 답변이 여러 개인 경우 입력에서 마지막에 나타나는 답변을 반환합니다.

findRedundantConnection(edges: List[List[int]]) -> List[int] 함수를 작성하세요.

제약

•n == len(edges)
•3 <= n <= 1000
•edges[i].length == 2
•1 <= ai < bi <= n
•ai != bi

예

Example 1

Input

edges = [[1,2],[1,3],[2,3]]

Output

[2,3]

Explanation

Removing edge [2,3] breaks the cycle 1-2-3-1, leaving a valid tree 1-2 and 1-3.

Example 2

Input

edges = [[1,2],[2,3],[3,4],[1,4],[1,5]]

Output

[1,4]

Explanation

The cycle is 1-2-3-4-1. The last edge in the input that is part of this cycle is [1,4].

Need a Hint?

세트나 힙과 같은 그래프 관련 데이터 구조를 사용해 보세요.

Edge Cases to Watch

빈 입력 구조
단일 요소 입력
큰 수치 범위

해결할 준비가 되셨나요?

Open the problem in PyRun's browser-based Python editor. Your code runs fully offline — no server required.

편집기에서 열기

인터뷰 통찰력 및 변형

그래프 접근 방식의 논리를 설명하세요.

null 또는 빈 입력과 같은 극단적인 경우에 대해 논의합니다.

복잡성 분석 분석

무차별 대입 복잡성

Time: O(n)•Space: O(1)

왜 시간인가?: Directly evaluates all possibilities.

왜 우주인가?: Uses standard local memory.

최적화된 복잡성

Time: O(n)•Space: O(1)

왜 시간인가?: Optimized paths reduce total operations.

왜 우주인가?: May trade memory for speed.

최적화된 솔루션 Python 코드

컴파일러에서 시도해 보세요

def find_redundant_connection_opt(edges):
    par = [i for i in range(len(edges) + 1)]
    rank = [1] * (len(edges) + 1)
    def find(n):
        p = par[n]
        while p != par[p]:
            par[p] = par[par[p]]
            p = par[p]
        return p
    def union(n1, n2):
        p1, p2 = find(n1), find(n2)
        if p1 == p2: return False
        if rank[p1] > rank[p2]:
            par[p2] = p1
            rank[p1] += rank[p2]
        else:
            par[p1] = p2
            rank[p2] += rank[p1]
        return True
    for n1, n2 in edges:
        if not union(n1, n2): return [n1, n2]

무차별 대입 코드(스포일러 보호)

컴파일러에서 시도해 보세요

def find_redundant_connection_brute(edges):
    adj = collections.defaultdict(list)
    def dfs(u, v, visit):
        if u == v: return True
        visit.add(u)
        for neighbor in adj[u]:
            if neighbor not in visit:
                if dfs(neighbor, v, visit): return True
        return False
    for u, v in edges:
        if u in adj and v in adj and dfs(u, v, set()): return [u, v]
        adj[u].append(v); adj[v].append(u)