冗余连接II
在一棵树中，边的数量比点的数量少1，因为多了一条附加边，所以点的数量和边的数量相同，都为$N$。
树中的每个节点都有一个父节点，除了根节点没有父节点。在多了一条附加的边之后，可能有以下两种情况：
附加的边指向根节点，则包括根节点在内的每个节点都有一个父节点，此时图中一定有环路；
附加的边指向非根节点，则恰好有一个节点（即被附加的边指向的节点）有两个父节点，此时图中可能有环路也可能没有环路。
具体做法是，使用数组 $\textit{parent}$ 记录每个节点的父节点，初始时对于任何 $1 \le i \le N$都有 $\textit{parent}[i]=i$，另外创建并查集，初始时并查集中的每个节点都是一个连通分支，该连通分支的根节点就是该节点本身。遍历每条边的过程中，维护导致冲突的边和导致环路出现的边，由于只有一条附加的边，因此最多有一条导致冲突的边和一条导致环路出现的边。
当访问到边$ [u,v]$ 时，进行如下操作：
如果此时已经有$ \textit{parent}[v] \ne v$，说明 $v$ 有两个父节点，将当前的边$ [u,v]$ 记为导致冲突的边；
否则，令 $\textit{parent}[v] = u$，然后在并查集中分别找到 $u$ 和 $v$ 的祖先（即各自的连通分支中的根节点），如果祖先相同，说明这条边导致环路出现，将当前的边$ [u,v]$ 记为导致环路出现的边，如果祖先不同，则在并查集中将 $u$ 和 $v$ 进行合并。
根据上述操作，同一条边不可能同时被记为导致冲突的边和导致环路出现的边。如果访问到的边确实同时导致冲突和环路出现，则这条边被记为导致冲突的边。
在遍历图中的所有边之后，根据是否存在导致冲突的边和导致环路出现的边，得到附加的边。
如果没有导致冲突的边，说明附加的边一定导致环路出现，而且是在环路中的最后一条被访问到的边，因此附加的边即为导致环路出现的边。
如果有导致冲突的边，记这条边为$ [u,v]$，则有两条边指向 $v$，另一条边为$ [\textit{parent}[v],v]$，需要通过判断是否有导致环路的边决定哪条边是附加的边。
如果有导致环路的边，则附加的边不可能是$ [u,v]$（因为$ [u,v]$ 已经被记为导致冲突的边，不可能被记为导致环路出现的边），因此附加的边是$ [\textit{parent}[v],v]$。
如果没有导致环路的边，则附加的边是后被访问到的指向 $v$ 的边，因此附加的边是$ [u,v]$。
1 | class Solution { |
2 | public int[] findRedundantDirectedConnection(int[][] edges) { |
3 | int[] ans = new int[2]; |
4 | int n = edges.length; |
5 | DSU dsu = new DSU(n+1); |
6 | int conflict = -1; |
7 | int cycle = -1; |
8 | int[] parent = new int[n+1]; |
9 | for(int i=1; i<=n; i++){ |
10 | parent[i] = i; |
11 | } |
12 | for(int i=0; i<n; i++){ |
13 | int a = edges[i][0]; |
14 | int b = edges[i][1]; |
15 | if(parent[b] != b){ |
16 | conflict = i; |
17 | }else{ |
18 | parent[b] = a; |
19 | if(dsu.find(a) == dsu.find(b)){ |
20 | cycle = i; |
21 | }else{ |
22 | dsu.merge(a, b); |
23 | } |
24 | } |
25 | } |
26 | if(conflict < 0){ |
27 | ans = edges[cycle]; |
28 | }else{ |
29 | int[] conflictEdge = edges[conflict]; |
30 | if(cycle >= 0){ |
31 | ans = new int[]{parent[conflictEdge[1]], conflictEdge[1]}; |
32 | }else{ |
33 | ans = new int[]{conflictEdge[0], conflictEdge[1]}; |
34 | } |
35 | } |
36 | return ans; |
37 | } |
38 | } |
39 | |
40 | class DSU{ |
41 | int[] p; |
42 | int[] rank; |
43 | |
44 | public DSU(int n){ |
45 | p = new int[n]; |
46 | rank = new int[n]; |
47 | reset(); |
48 | } |
49 | |
50 | public void reset(){ |
51 | for(int i=0; i<p.length; i++){ |
52 | p[i] = i; |
53 | rank[i] = 0; |
54 | } |
55 | } |
56 | |
57 | public int find(int x){ |
58 | if(p[x]==p[p[x]]){ |
59 | return p[x]; |
60 | } |
61 | return p[x] = find(p[x]); |
62 | } |
63 | |
64 | public void merge(int a, int b){ |
65 | a = find(a); |
66 | b = find(b); |
67 | if(a == b){ |
68 | return; |
69 | } |
70 | if(rank[a] == rank[b]){ |
71 | rank[a]++; |
72 | } |
73 | if(rank[a] < rank[b]){ |
74 | int tmp = a; |
75 | a = b; |
76 | b = tmp; |
77 | } |
78 | p[b] = a; |
79 | } |
80 | } |
复杂度分析：
- 时间复杂度：$O(NlogN)$。
- 空间复杂度：$O(N)$。