1
# Runtime: 118 ms (Top 30.98%) | Memory: 14.6 MB (Top 46.10%)
2
class Solution:
3
    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:
4
        # THREE DIFFERENT TYPES OF REDUNDANT TREES CAN EXISIT IDENTIFY THOSE (CYCLE,NOCYCLE,INDEGREE2)
5
        # CAN BE SOLVED USING DSU OR DFS
6
        class DSU:
7
            def __init__(self, n):
8
                self.parent = [i for i in range(1005)]
9

10
            def find(self, node):
11
                if self.parent[node] == node:
12
                    return node
13
                self.parent[node] = self.find(self.parent[node])
14
                return self.parent[node]
15

16
            def union(self, node1, node2):
17
                p1 = self.find(node1)
18
                p2 = self.find(node2)
19
                if p1 != p2:
20
                    self.parent[p1] = p2
21

22
            def isConnected(self, node1, node2):
23
                return self.find(node1) == self.find(node2)
24

25
        def isValidTree(edges, edge, n):
26
            d = DSU(n)
27
            for e in edges:
28
                if e == edge:
29
                    continue
30
                d.union(e[0], e[1])
31
            return d.isConnected(edge[0], edge[1])
32

33
        indegree = []
34
        count = defaultdict(int)
35
        for i, j in edges:
36
            count[j] = count.get(j, 0) + 1
37
        n = len(edges)
38
        for i in range(n):
39
            if count[edges[i][1]] == 2:
40
                indegree += [i]
41
        if len(indegree) != 0:
42
            if isValidTree(edges, edges[indegree[-1]], n):
43
                return edges[indegree[-1]]
44
            return edges[indegree[0]]
45
        else:
46
            d2 = DSU(n)
47
            for e in edges:
48
                if d2.isConnected(e[0], e[1]):
49
                    return e
50
                d2.union(e[0], e[1])
51

52

53
# def dfs(node):
54
# if node in seen:
55
# return False
56
# seen.add(node)
57
# for nb in g[node]:
58
# if not dfs(nb):
59
# return False
60
# return True
61
# g = defaultdict(list)
62
# v = defaultdict(int)
63
# total = set()
64
# for i,j in edges:
65
# g[i] = g.get(i,[]) + [j]
66
# v[j] = v.get(j,0) + 1
67
# total.add(i)
68
# total.add(j)
69
# for e in edges[::-1]:
70
# g[e[0]].remove(e[1])
71
# v[e[1]] -= 1
72
# for root in total:
73
# seen = set()
74
# if v[root] == 0 and dfs(root) and len(seen) == len(total):
75
# return e
76

77
# v[e[1]] += 1
78
# g[e[0]].append(e[1])
79
# return [-1,-1]