Leetcode 684. Redundant Connection (python)

题目

解法1：dfs

一次构建图，返回第一组成环的边。

class Solution:def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:def dfs(source,target):if source in seen:return seen.add(source)if source == target:return Trueflag = Falsefor nei in graph[source]:flag = flag or dfs(nei,target)return flaggraph = collections.defaultdict(set)for u,v in edges:seen = set()if u in graph and v in graph and dfs(u,v):return u,vgraph[u].add(v)graph[v].add(u)

解法2：unionfind

python版本：

class Solution:def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:def find(p):while p != _id[p]:p = _id[p]return pdef union(p,q):_id[find(p)] = find(q)def isconnected(p,q):return find(q) == find(p)n = len(edges)_id = [0]*(n+1)for i in range(n+1):_id[i] = ifor edge in edges:u = edge[0]v = edge[1]if isconnected(u,v):return edgeunion(u,v)return [-1,-1]

c++版本：

class UF{
    vector<int> id;
public:UF(int n):id(n){
    for (int i=0;i<n;i++){
    id[i] = i;}}int find(int p){
    while (p != id[p]){
    p = id[p];}return p;}void union_node(int p, int q){
    id[find(p)] = find(q);}bool isConnected(int p,int q){
    return find(p) == find(q);}
};
class Solution {
    
public:vector<int> findRedundantConnection(vector<vector<int>>& edges) {
    int n = edges.size();UF uf(n+1);for (auto e:edges){
    int u=e[0], v=e[1];if (uf.isConnected(u,v)){
    return e;}uf.union_node(u,v);}return {
    -1,-1};}
};