LeetCode 85. 冗余连接 II

2019-03-18 18:15 by Vizdl, … 阅读, … 评论, 收藏, 编辑

题目:　

　　在本问题中，有根树指满足以下条件的有向图。该树只有一个根节点，所有其他节点都是该根节点的后继。每一个节点只有一个父节点，除了根节点没有父节点。

输入一个有向图，该图由一个有着N个节点 (节点值不重复1, 2, …, N) 的树及一条附加的边构成。附加的边的两个顶点包含在1到N中间，这条附加的边不属于树中已存在的边。

结果图是一个以边组成的二维数组。 每一个边 的元素是一对 [u, v]，用以表示有向图中连接顶点 u and v和顶点的边，其中父节点u是子节点v的一个父节点。

返回一条能删除的边，使得剩下的图是有N个节点的有根树。若有多个答案，返回最后出现在给定二维数组的答案。

示例:

　　　　　　输入: [[1,2], [1,3], [2,3]]
　　　　　　输出: [2,3]
　　　　　　解释: 给定的有向图如下:
　　　　　　  1
　　　　　　 / \
　　　　　　v   v
　　　　　　2-->3


　　　　　　输入: [[1,2], [2,3], [3,4], [4,1], [1,5]]
　　　　　　输出: [4,1]
　　　　　　解释: 给定的有向图如下:
　　　　　　5 <- 1 -> 2
　　　　　　     ^    |
　　　　　　     |    v
　　　　　　     4 <- 3

题解:
　　在以上题目中有一句比较关键的句子 : 该图由一个有着N个节点 (节点值不重复1, 2, ..., N) 的树及一条附加的边构成。附加的边
的两个顶点包含在1到N中间，这条附加的边不属于树中已存在的边。
　　这句话其实是引导我们思路的,我们可以知道题目所说的有根树具有三个性质。第一,有根树存在入度为0的节点(根节点),第二有根树除了
根节点其他节点的入度都为1。第三有根树所有节点都是连通的。
　　　　如若一颗有根树加上一条边的话,那么加上的边存在以下三种情况:
　　　　1)边的两端是同一节点 
　　　　　　判定方式 : 直接看两遍是否相等
　　　　　　处理 : 直接可以知道这条边肯定不是原有的,返回当前边
　　　　2)两端不是同一节点,并且被指向的是根节点。
　　　　　　判定方式 : 如若被指向的那端统计之后出现了所有节点或者不存在入度为2的节点
　　　　　　处理 : 因为根被指向了后一定会形成环,故而处理的可能性很多(除去环内任意边),但是需要注意是否存在示例2中的情况,如若除去边[1,5],就会导致该有根树不连通,并且依然有环。 因为是否连通使用并查集很容易检测是否连通
,故而这里我选择了直接使用并查集。
　　　　3）两端不是同一节点,并且被指向的是非根节点。
　　　　　　判定方式 : 剩下的情况都是3)//存在入度为2的节点
　　　　　　处理 : 因为存在入度为2的节点,所以在这就是在两条指向入度为2节点内直接二选一,但是这里不能随便选,必须保证如若因为这条边成环(例如示例一加上一个节点4并且4指向2),也就是 : [[4, 2],[1,2], [1,3], [2,3]]
,这时指向2的一共有两个节点 4 和 1,这时候如若选择删除[1,2]则会导致整张图不连通,故而需要检查连通性来选择删除两个节点的哪个,依然使用并查集。
代码:
 1 int n;
 2     public int[] findRedundantDirectedConnection(int[][] edges) {
 3         this.n = edges.length;
 4         int[] table = new int[n];
 5         Arrays.fill(table, -1);
 6         int other = -1;
 7         for (int i = 0; i < n; i++) {
 8             if (edges[i][0] == edges[i][1]) {
 9                 return edges[i];
10             }
11             int index = edges[i][1] - 1;
12             if (table[index] != -1) {
13                 other = i;
14             } else {
15                 table[index] = i;
16             }
17         }
18         // 如若指向非根
19         if (other != -1) {
20             // 且 如若删除了后面那个节点 仍然是 连通的。
21             if (this.isConnected(edges, other))
22                 return edges[other];
23             else
24                 return edges[table[edges[other][1] - 1]];
25         }
26         for (int i = n - 1; i >= 0; i--) {
27             //如若除去i还是连通的
28             if (this.isConnected(edges, i)) {
29                 return edges[i];
30             }
31         }
32         return new int[] {};
33     }
34 
35     /**
36      * 若除去第i条边
37      * 
38      * @param edges
39      * @param i
40      * @return
41      */
42     int[] table;
43 
44     public boolean isConnected(int[][] edges, int i) {
45         this.table = new int[n];
46         for (int j = 0; j < n; j++) {
47             table[j] = j;
48         }
49         for (int j = 0; j < n; j++) {
50             if (j != i)
51                 union(edges[j][0] - 1, edges[j][1] - 1);
52         }
53         boolean flag = true;
54         for (int k = 0; k < n; k++) {
55             if (table[k] == k) {
56                 if (flag) {
57                     flag = false;
58                 } else {
59                     return false;
60                 }
61             }
62         }
63         return true;
64     }
65 
66     public boolean union(int i, int j) {
67         int iIndex = this.find(i);
68         int jIndex = this.find(j);
69         if (iIndex == jIndex) {
70             return false;
71         }
72         table[iIndex] = jIndex;
73         return true;
74     }
75 
76     public int find(int i) {
77         while (table[i] != i) {
78             i = table[i];
79         }
80         return i;
81     }

 


 
版权声明：本文为vizdl原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/vizdl/p/10553895.html