Interview 150
Redundant Connection
- Problem
- LC 684
- File
- interview150_LC684RedundantConnection.java
- Path
- pkg5leetcode/interview150/interview150_LC684RedundantConnection.java
- Package
- pkg5leetcode.interview150
- Command
- java pkg5leetcode/interview150/interview150_LC684RedundantConnection.java
There is no in-browser runner. This is the file from the curriculum, unchanged.
1package pkg5leetcode.interview150;2 3/** LC 684 Redundant Connection */4public class interview150_LC684RedundantConnection {5 static int find(int[] p, int x) { return p[x] == x ? x : (p[x] = find(p, p[x])); }6 7 static int[] findRedundantConnection(int[][] edges) {8 int n = edges.length;9 int[] p = new int[n + 1];10 for (int i = 0; i <= n; i++) p[i] = i;11 for (int[] e : edges) {12 int a = find(p, e[0]), b = find(p, e[1]);13 if (a == b) return e;14 p[a] = b;15 }16 return new int[0];17 }18 19 public static void main(String[] args) {20 System.out.println(java.util.Arrays.toString(findRedundantConnection(new int[][]{{1,2},{1,3},{2,3}})));21 }22}