108. 冗余連接

卡碼網題目鏈接（ACM模式）(opens new window)

題目描述

有一個圖，它是一棵樹，他是擁有 n 個節點（節點編號1到n）和 n - 1 條邊的連通無環無向圖（其實就是一個線形圖），如圖：

現在在這棵樹上的基礎上，添加一條邊（依然是n個節點，但有n條邊），使這個圖變成了有環圖，如圖

先請你找出冗余邊，刪除后，使該圖可以重新變成一棵樹。

輸入描述

第一行包含一個整數 N，表示圖的節點個數和邊的個數。

后續 N 行，每行包含兩個整數 s 和 t，表示圖中 s 和 t 之間有一條邊。

輸出描述

輸出一條可以刪除的邊。如果有多個答案，請刪除標準輸入中最后出現的那條邊。

輸入示例

3
1 2
2 3
1 3

輸出示例

1 3

提示信息

圖中的 1 2，2 3，1 3 等三條邊在刪除后都能使原圖變為一棵合法的樹。但是 1 3 由于是標準輸入里最后出現的那條邊，所以輸出結果為 1 3

數據范圍：

1 <= N <= 1000.

我們就可以從前向后遍歷每一條邊（因為優先讓前面的邊連上），邊的兩個節點如果不在同一個集合，就加入集合（即：同一個根節點）。

如圖所示，節點A 和節點 B 不在同一個集合，那么就可以將兩個 節點連在一起。

如果邊的兩個節點已經出現在同一個集合里，說明著邊的兩個節點已經連在一起了，再加入這條邊一定就出現環了。

如圖所示：

已經判斷 節點A 和 節點B 在在同一個集合（同一個根），如果將 節點A 和 節點B 連在一起就一定會出現環。

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;}}

109. 冗余連接II

卡碼網題目鏈接（ACM模式）(opens new window)

題目描述

有一種有向樹,該樹只有一個根節點，所有其他節點都是該根節點的后繼。該樹除了根節點之外的每一個節點都有且只有一個父節點，而根節點沒有父節點。有向樹擁有 n 個節點和 n - 1 條邊。如圖：

現在有一個有向圖，有向圖是在有向樹中的兩個沒有直接鏈接的節點中間添加一條有向邊。如圖：

輸入一個有向圖，該圖由一個有著 n 個節點(節點編號 從 1 到 n)，n 條邊，請返回一條可以刪除的邊，使得刪除該條邊之后該有向圖可以被當作一顆有向樹。

輸入描述

第一行輸入一個整數 N，表示有向圖中節點和邊的個數。

后續 N 行，每行輸入兩個整數 s 和 t，代表這是 s 節點連接并指向 t 節點的單向邊

輸出描述

輸出一條可以刪除的邊，若有多條邊可以刪除，請輸出標準輸入中最后出現的一條邊。

輸入示例

3
1 2
1 3
2 3

輸出示例

2 3

提示信息

在刪除 2 3 后有向圖可以變為一棵合法的有向樹，所以輸出 2 3

數據范圍：

1 <= N <= 1000.

本題的本質是 ：有一個有向圖，是由一顆有向樹 + 一條有向邊組成的 （所以此時這個圖就不能稱之為有向樹），現在讓我們找到那條邊 把這條邊刪了，讓這個圖恢復為有向樹。

還有“若有多條邊可以刪除，請輸出標準輸入中最后出現的一條邊”，這說明在兩條邊都可以刪除的情況下，要刪順序靠后的邊！

我們來想一下 有向樹的性質，如果是有向樹的話，只有根節點入度為0，其他節點入度都為1（因為該樹除了根節點之外的每一個節點都有且只有一個父節點，而根節點沒有父節點）。

所以情況一：如果我們找到入度為2的點，那么刪一條指向該節點的邊就行了。

如圖：

找到了節點3 的入度為2，刪 1 -> 3 或者 2 -> 3 。選擇刪順序靠后便可。

但 入度為2 還有一種情況，情況二，只能刪特定的一條邊，如圖：

節點3 的入度為 2，但在刪除邊的時候，只能刪 這條邊（節點1 -> 節點3），如果刪這條邊（節點4 -> 節點3），那么刪后本圖也不是有向樹了（因為找不到根節點）。

綜上，如果發現入度為2的節點，我們需要判斷 刪除哪一條邊，刪除后本圖能成為有向樹。如果是刪哪個都可以，優先刪順序靠后的邊。

情況三： 如果沒有入度為2的點，說明 圖中有環了（注意是有向環）。

如圖：

對于情況三，刪掉構成環的邊就可以了。

import java.util.*;/* * 冗余連接II。主要問題是存在入度為2或者成環，也可能兩個問題同時存在。* 1.判斷入度為2的邊 * 2.判斷是否成環（并查集）*/public class Main {/*** 并查集模板*/static class Disjoint {private final int[] father;public Disjoint(int n) {father = new int[n];for (int i = 0; i < n; i++) {father[i] = i;}}public void join(int n, int m) {n = find(n);m = find(m);if (n == m) return;father[n] = m;}public int find(int n) {return father[n] == n ? n : (father[n] = find(father[n]));}public boolean isSame(int n, int m) {return find(n) == find(m);}}static class Edge {int s;int t;public Edge(int s, int t) {this.s = s;this.t = t;}}static class Node {int id;int in;int out;}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();List<Edge> edges = new ArrayList<>();Node[] nodeMap = new Node[n + 1];for (int i = 1; i <= n; i++) {nodeMap[i] = new Node();}Integer doubleIn = null;for (int i = 0; i < n; i++) {int s = scanner.nextInt();int t = scanner.nextInt();//記錄入度nodeMap[t].in++;if (!(nodeMap[t].in < 2)) doubleIn = t;Edge edge = new Edge(s, t);edges.add(edge);}Edge result = null;//存在入度為2的節點，既要消除入度為2的問題同時解除可能存在的環if (doubleIn != null) {List<Edge> doubleInEdges = new ArrayList<>();for (Edge edge : edges) {if (edge.t == doubleIn) doubleInEdges.add(edge);if (doubleInEdges.size() == 2) break;}Edge edge = doubleInEdges.get(1);if (isTreeWithExclude(edges, edge, nodeMap)) {result = edge;} else {result = doubleInEdges.get(0);}} else {//不存在入度為2的節點,則只需要解除環即可result = getRemoveEdge(edges, nodeMap);}System.out.println(result.s + " " + result.t);}public static boolean isTreeWithExclude(List<Edge> edges, Edge exculdEdge, Node[] nodeMap) {Disjoint disjoint = new Disjoint(nodeMap.length + 1);for (Edge edge : edges) {if (edge == exculdEdge) continue;//成環則不是樹if (disjoint.isSame(edge.s, edge.t)) {return false;}disjoint.join(edge.s, edge.t);}return true;}public static Edge getRemoveEdge(List<Edge> edges, Node[] nodeMap) {int length = nodeMap.length;Disjoint disjoint = new Disjoint(length);for (Edge edge : edges) {if (disjoint.isSame(edge.s, edge.t)) return edge;disjoint.join(edge.s, edge.t);}return null;}}