Description

Submission

class Solution {
    unordered_map<int, int> inDegree;
    unordered_map<int, int> outDegree;
    unordered_map<int, vector<int>> graph;
    vector<int> path;

    void dfs(int node) {
        while(!graph[node].empty()) {
            int nextNode = graph[node].back();
            graph[node].pop_back();
            dfs(nextNode);
        }
        path.push_back(node);
    }
public:
    vector<vector<int>> validArrangement(vector<vector<int>>& pairs) {
        for(auto& p: pairs) {
            int a = p[0], b = p[1];
            ++inDegree[b];
            ++outDegree[a];
            graph[a].push_back(b);
        }

        int start = pairs[0][0];
        for(auto& p: graph) {
            int x = p.first;
            if(outDegree[x] - inDegree[x] == 1) {
                start = x;
                break;
            }
        }

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