# 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]]))