108. 冗余连接

题目描述

        有一个图，它是一棵树，他是拥有 n 个节点（节点编号1到n）和 n - 1 条边的连通无环无向图，例如如图：

现在在这棵树上的基础上，添加一条边（依然是n个节点，但有n条边），使这个图变成了有环图，如图：

先请你找出冗余边，删除后，使该图可以重新变成一棵树。

输入描述

        第一行包含一个整数 N，表示图的节点个数和边的个数。

        后续 N 行，每行包含两个整数 s 和 t，表示图中 s 和 t 之间有一条边。

输出描述

        输出一条可以删除的边。如果有多个答案，请删除标准输入中最后出现的那条边。

import java.util.Scanner;

public class Main {
    private static int[] father;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int pointNum = scanner.nextInt();
        father = new int[pointNum + 1];
        init();
        for (int i = 0; i < pointNum; i++) {
            //该方法得实现中有判断如果已经属于同一个集合后得处理
            join(scanner.nextInt(), scanner.nextInt());
        }
    }

    /**
     * 并查集初始化
     */
    private static void init() {
        for (int i = 1; i < father.length; i++) {
            // 让每个元素指向自己
            father[i] = i;
        }
    }

    /**
     * 并查集寻根
     *
     * @param u
     * @return
     */
    private static int find(int u) {
        // 判断 u 是否等于自己，如果是的话，直接返回自己
        // 如果不等于自己，就寻找根，寻找的时候，反复进行路径压缩
        return u == father[u] ? u : (father[u] = find(father[u]));
    }

    /**
     * 判断 u 和 v 是否同根
     *
     * @param u
     * @param v
     * @return
     */
    private static boolean isSame(int u, int v) {
        return find(u) == find(v);
    }

    /**
     * 添加 边 到并查集，v 指向 u
     *
     * @param u
     * @param v
     */
    private static void join(int u, int v) {
        // --if-- 如果两个点已经同根，说明他们的信息已经存储到并查集中了，直接返回即可
        // 寻找u的根
        int uRoot = find(u);
        // 寻找v的根
        int vRoot = find(v);
        if (uRoot == vRoot) {
            // --if-- 如果u,v的根相同，说明两者已经连接了，直接输出
            System.out.println(u + " " + v);
            return;
        }
        // --if-- 将信息添加到并查集
        father[vRoot] = uRoot;
    }

}

冗余连接II 下次再做吧，有点难。