1
class Solution {
2
  int[] dsu;
3

4
  public int[] findRedundantDirectedConnection(int[][] edges) {
5
    int n = edges.length;
6
    int[] parent = new int[n + 1];
7
    Arrays.fill(parent, -1);
8

9
    int[] e2 = null;
10
    int[] e1 = null;
11
    boolean twopt = false;
12

13
    for (int[] edge : edges) {
14

15
      int from = edge[0];
16
      int to = edge[1];
17

18
      if (parent[to] == -1) {
19
        parent[to] = from;
20
      } else {
21
        twopt = true;
22
        e2 = edge;
23
        e1 = new int[] {parent[to], to};
24
        break;
25
      }
26
    }
27

28
    dsu = new int[edges.length + 1];
29
    for (int i = 0; i <= edges.length; i++) {
30
      dsu[i] = i;
31
    }
32
    if (twopt == false) {
33
      int[] res = null;
34

35
      for (int[] edge : edges) {
36
        int from = edge[0];
37
        int to = edge[1];
38

39
        int fromlead = find(from);
40
        if (fromlead == to) {
41
          res = edge;
42
          break;
43
        } else {
44
          dsu[to] = fromlead;
45
        }
46
      }
47
      return res;
48
    } else {
49
      boolean iscycle = false;
50
      for (int[] edge : edges) {
51
        if (edge == e2) continue;
52
        int from = edge[0];
53
        int to = edge[1];
54

55
        int fromlead = find(from);
56

57
        if (fromlead == to) {
58
          iscycle = true;
59
          break;
60
        } else {
61
          dsu[to] = fromlead;
62
        }
63
      }
64
      if (iscycle == true) {
65
        return e1;
66
      } else {
67
        return e2;
68
      }
69
    }
70
  }
71

72
  public int find(int x) {
73
    if (dsu[x] == x) return x;
74
    return dsu[x] = find(dsu[x]);
75
  }
76
}