package question;

/*
 @author: Roderland
 @create: 2020年09月23日---13:30
*/
public class Question684 {
 public static void main(String[] args) {
 Point[] a = new Point[1];
 for (Point point : a) {
 point = new Point();
 }
 for (Point p : a) {
 System.out.println(p);
 }
 }

 public int[] findRedundantConnection(int[][] edges) {
 Point[] points = new Point[edges.length-1];
 for (int[] edge : edges) {
 Point point0 = points[edge[0]];
 Point point1 = points[edge[1]];
 if (point0 != null && point1 != null) {
 if (findRoot(point0) == findRoot(point1)) return edge;
 findRoot(point1).parent = points[edge[0]];
 } else if (point0 != null) {
 points[edge[1]] = new Point(point0);
 } else if (point1 != null) {
 points[edge[0]] = new Point(point1);
 } else {
 Point root = new Point();
 points[edge[0]] = new Point(root);
 points[edge[1]] = new Point(points[edge[0]]);
 }
 }
 return null;
 }

 public Point findRoot(Point point) {
 if (point.parent == null) return point;
 else return findRoot(point.parent);
 }
}

class Point {
 Point parent;

 public Point() {
 }

 public Point(Point parent) {
 this.parent = parent;
 }
}

class FindRedundantConnection2 {
 int[] root;
 public int[] findRedundantConnection(int[][] edges) {
 root=new int[edges.length+1];
 for (int i = 0; i < root.length; i++) {
 root[i]=i;
 }
 for (int[] edge : edges) {
 if (merge(edge[0], edge[1])) {
 return edge;
 }
 }
 return null;
 }

 private boolean merge(int x, int y) {
 x=find(x);
 y=find(y);
 if (x==y)return true;
 root[x]=y;
 return false;
 }

 private int find(int x) {
 if (root[x]==x) return x;
 return root[x]=find(root[x]);
 }
}