Redundant Connection
并查集模板题
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
class Solution { class uf{ int[] p; int n; public uf(int n){ this.n = n + 1; this.p = new int[n + 1]; for(int i = 1; i <= n; i++) this.p[i] = i; } public int find(int n){ if(p[n] == n) return n; p[n] = find(p[n]); return p[n]; } public void union(int a, int b){ int ra = find(a); int rb = find(b); if(ra == rb) return; if(ra < rb) p[ra] = rb; else p[rb] = ra; } } public int[] findRedundantConnection(int[][] edges) { int n = edges.length; uf u = new uf(n); for(int[] e : edges){ if(u.find(e[0]) != u.find(e[1])) u.union(e[0], e[1]); else return e; } return null; } } |