2097. Valid Arrangement of Pairs

문제

You are given a 0-indexed 2D integer array pairs where pairs[i] = [starti, endi]. An arrangement of pairs is valid if for every index i where 1 <= i < pairs.length, we have endi-1 == starti.

Return any valid arrangement of pairs.

Note: The inputs will be generated such that there exists a valid arrangement of pairs.

• 시작지점과 끝점 노드로 구성된 pairs가 있다
• 이를 이용해 오일러 경로를 구하라

예시

[[5,1],[4,5],[11,9],[9,4]]

[[11,9],[9,4],[4,5],[5,1]]

제한

• $1 <= pairs.length <= 10^5$
• $pairs[i].length == 2$
• $0 <= start_i, end_i <= 10^9$
• $start_i != end_i$
• 같은 pair는 없다.
• 반드시 정답이 존재한다.

풀이

• 시작정점을 찾은 뒤 그리디하게 찾아 나가면 된다.

class Solution:
    def validArrangement(self, pairs: List[List[int]]) -> List[List[int]]:
        graph = defaultdict(list)
        in_degree = defaultdict(int)
        out_degree = defaultdict(int)

        for start, end in pairs:
            graph[start].append(end)
            out_degree[start] += 1
            in_degree[end] += 1

        start_node = None
        for node in in_degree.keys() | out_degree.keys():
            if out_degree[node] - in_degree[node] == 1:
                start_node = node
                break
        if start_node is None:
            start_node = pairs[0][0]  

        path = []
        stack = [start_node]

        while stack:
            node = stack[-1]
            if graph[node]:
                next_node = graph[node].pop()
                stack.append(next_node)
                print('append')
            else:
                path.append(stack.pop())
                print('pop')

        path.reverse()

        edges = [[path[i], path[i+1]] for i in range(len(path) - 1)]
        return edges