---
title: 684. Redundant Connection
tags: graph
description: share source code.
---

# 684. Redundant Connection

class Solution {

    public int[] findRedundantConnection(int[][] edges) {
        int n = edges.length;
        List<Integer>[] graph = new ArrayList[n + 1];
        Arrays.setAll(graph, v -> new ArrayList<>());
        
        for(int edge [] : edges){
          
            if(dfs(graph, edge[0], -1, edge[1])){
                return edge;
            }
            
            graph[edge[0]].add(edge[1]);
            graph[edge[1]].add(edge[0]);
        }
        
        return null;
    }
    
    public boolean dfs(List<Integer>[] graph, int u, int p, int end){
        if(u == end){
            return true;
         }
        
        for(int v : graph[u]){
            if(v == p || v == -1){
                continue;
            }
            
            if(dfs(graph,  v, u, end)){
                return true;
            }
            
        }
        
        return false;
    }
}