[LeetCode] 2097. Valid Arrangement of Pairs

https://leetcode.com/problems/valid-arrangement-of-pairs/description/

leetcode - Valid Arrangement of Pairs

문제 유형: 그래프, 오일러 경로, 오일러 회로, dfs

문제 난이도: Hard

 

문제

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.

 

0-indexed의 2D배열 pairs가 주어진다.

pairs는 [start, end]로 구성된다.

1 <= i < pairs.length에 대해  end_i-1이 start_i와 같으면 valid하다고 합니다.

pairs를 재배열하여 valid하게 만드시오.

 

풀이

이 문제는 오일러 경로/회로 문제이다.

pairs의 각 요소들을 간선이라고 생각하면 된다.

방향 그래프이므로, 진출차수가 진입차수보다 1 크다면 그 부분이 시작이고, 따로 그런부분이 없다면 임의의 점에서 시작해도 된다.

 

순회한 경로를 간선으로 재배치해주면 된다

 

코드

C++

class Solution {
public:
    vector<vector<int>> validArrangement(vector<vector<int>>& pairs) {
        unordered_map<int, vector<int>> adj;
        unordered_map<int, int> indegree;
        unordered_map<int, int> outdegree;

        for (const auto& pair : pairs) {
            int u = pair[0], v = pair[1];
            adj[u].push_back(v);
            outdegree[u]++;
            indegree[v]++;
        }

        int start = pairs[0][0];
        for (const auto& node : adj) {
            if (outdegree[node.first] - indegree[node.first] == 1) {
                start = node.first;
                break;
            }
        }

        // Hierholzer's Algorithm
        vector<int> path;
        stack<int> stk;
        stk.push(start);

        while (!stk.empty()) {
            int curr = stk.top();
            if (!adj[curr].empty()) {
                stk.push(adj[curr].back());
                adj[curr].pop_back();
            } else {
                path.push_back(curr);
                stk.pop();
            }
        }

        vector<vector<int>> ans;
        for (int i = path.size() - 1; i > 0; --i) {
            ans.push_back({path[i], path[i - 1]});
        }

        return ans;
    }
};