aboutsummaryrefslogtreecommitdiff
path: root/valid_arrangement_pairs.py
blob: 528c8832ba53feab9a015ad4726f932827ab29fe (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
# 2097. Valid Arrangement of Pairs
from collections import defaultdict

"""
you are given a 0-indexed 2d integer array 'pairs' where 'pairs[i] =
[start_i, end_i]'. an arrangement of 'pairs' is valid for every index 'i'
where '1 <= i < pairs.length', we have 'end_i-1 == start_i'. return any valid
arrangement of 'pairs'. note, the inputs will be generated such that there
exists a valid arrangement of 'pairs'.
"""


class Solution(object):
    def validArrangement(self, pairs):
        """
        :type pairs: List[List[int]]
        :rtype: List[List[int]]
        """
        graph, degree = defaultdict(list), defaultdict(int)
        for x, y in pairs:
            graph[x].append(y)
            degree[x] += 1
            degree[y] -= 1
        for k in degree:
            if degree[k] == 1:
                x = k
                break
        ans = []

        def euler(x):
            while graph[x]:
                euler(graph[x].pop())
            ans.append(x)

        euler(x)
        ans.reverse()
        return [[ans[i], ans[i + 1]] for i in range(len(ans) - 1)]


if __name__ == "__main__":
    obj = Solution()
    print(obj.validArrangement(pairs=[[5, 1], [4, 5], [11, 9], [9, 4]]))
    print(obj.validArrangement(pairs=[[1, 3], [3, 2], [2, 1]]))
    print(obj.validArrangement(pairs=[[1, 2], [1, 3], [2, 1]]))