Redundant Connection

Medium (Trung bình) Python 🔗 Xem trên LeetCode

📋 Đề Bài

Chưa có mô tả.

🧠 Thuật Toán & Kỹ Thuật

DFS (Tìm kiếm theo chiều sâu)Hash Table (Bảng băm)Graph (Đồ thị)
⏱️ Thời gian O(V+E)
💾 Không gian O(V)

💻 Lời Giải

Python 0684-redundant-connection.py
class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        n = len(edges)
        visited = [False] * (n + 1)
        
        adj = defaultdict(list)
        
        def dfs(u, end):
            if u == end:
                return True
            visited[u] = True
            for v in adj[u]:
                if visited[v] == False:
                    if dfs(v, end):
                        return True
            return False
        
        for u, v in edges:
            if dfs(u, v):
                return [u, v]
            visited = [False] * (n + 1)
            adj[u].append(v)
            adj[v].append(u)
        
        return [-1, -1]