讨论/《深度优先搜索》 - 例题:冗余连接/
《深度优先搜索》 - 例题:冗余连接
共 3 个回复

BFS/DFS方法

class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        # 构建邻接表
        adj = defaultdict(list)
        visited = set()

        for edge in edges:
            u, v = edge 
            if u in adj and v in adj:
                visited.clear()
                # 搜索u, v之间是否存在边可以用DFS或者BFS
                #if self.dfs(adj, u, v, visited):
                if self.bfs(adj, u, v, visited):
                    return edge 
            adj[u].append(v)
            adj[v].append(u)
        
    def dfs(self, adj, source, target, visited):
        if source == target: return True 
        visited.add(source)
        for successor in adj[source]:
            if successor not in visited:
                if self.dfs(adj, successor, target, visited):
                    return True 
        return False 

    def bfs(self, adj, source, target, visited):
        que = collections.deque([source])
        visited.add(source)
        while que:
            top = que.popleft()
            if top == target: return True 
            for successor in adj[top]:
                if successor not in visited:
                    que.append(successor)
                    visited.add(successor)
        return False 
class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        dt = defaultdict(list)
        res = []
        def dfs(cur,src,dst,vstd):
            nonlocal res
            for j in dt[cur]:
                if cur != src and j == dst:
                    res = [src,dst]
                    return
                if not vstd & (1 << j):
                    vstd |= (1 << j)
                    dfs(j,src,dst,vstd)
        for edge in edges:
            dt[edge[0]].append(edge[1])
            dt[edge[1]].append(edge[0])
            dfs(edge[0],edge[0],edge[1],1 << edge[0] | 1 << edge[1])
        return res
class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        p = {}
        def find(x):
            p.setdefault(x,x)
            while x != p[x]:
                x = p[x]
            return x
        def union(x,y):
            p[find(x)] = find(y)
        def connected(x,y):
            return find(x) == find(y)
        def add(x):
            if x not in p:
                p[x] = None
        for edge in edges:
            if connected(edge[0],edge[1]): 
                res = [edge[0],edge[1]]
            else:
                union(edge[0],edge[1])
        return res