684. Redundant Connection

BFS

T: o(n^2)

S: o(n)

```java
class Solution {
    public int[] findRedundantConnection(int[][] edges) {
        int n = edges.length;
        Map<Integer, List<Integer>> graph = new HashMap<>();
        for (int i = 0; i < n; i++) {
            if (bfs(n, graph, edges[i][0], edges[i][1])) {
                return new int[] {edges[i][0], edges[i][1]};
            }
            graph.putIfAbsent(edges[i][0], new ArrayList<>());
            graph.get(edges[i][0]).add(edges[i][1]);
            graph.putIfAbsent(edges[i][1], new ArrayList<>());
            graph.get(edges[i][1]).add(edges[i][0]);
        }
        return new int[]{-1,-1};
    }
    private boolean bfs(int n, Map<Integer, List<Integer>> graph, int start, int end) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(start);
        boolean[] visited = new boolean[n+1];

        while (!queue.isEmpty()) {
            int cur = queue.poll();
            if (visited[cur]) {
                continue;
            }
            visited[cur] = true;
            if (cur == end) {
                return true;
            }
            if (graph.containsKey(cur)) {
                for (int next : graph.get(cur)) {
                    queue.offer(next);
                }
            }
            
        }
        return false;
    }
}

/*
bfs
O(n^2)
from beginging to build graph, one by one test edge, test if "edge start"" can reach "edge end"
no -> add edge to graph (build graph)


yes -> find the cycle
*/
```

union find

```java
class Solution {
    public int[] findRedundantConnection(int[][] edges) {
        int n = edges.length;
        UnionFind uf = new UnionFind(n);
        for (int[] edge : edges) {
            if (!uf.union(edge[0], edge[1])) {
                return new int[]{edge[0], edge[1]};
            }
        }
        return new int[]{-1, -1};
    }
    class UnionFind {
        int[] parent;
        UnionFind(int n) {
            parent = new int[n+1];
            for (int i = 0; i <= n; i++) {
                parent[i] = i;
            }
        }

        public boolean union(int x, int y) {
            int i = find(x);
            int j = find(y);
            if (i != j) {
                parent[i] = j;
                return true;
            }
            return false; // union fail
        }
        private int find(int x) {
            if (parent[x] != x) {
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }
    }
}
```