2097. Valid Arrangement of Pairs

T: O(V + E)
S: O(V + E)

class Solution {
    public int[][] validArrangement(int[][] pairs) {
        Map<Integer, Deque<Integer>> graph = new HashMap<>();
        Map<Integer, Integer> degree = new HashMap<>();
        for (int[] p : pairs) {
            int from = p[0];
            int to = p[1];
            graph.computeIfAbsent(from, k -> new ArrayDeque<>()).offer(to);
            degree.put(to, degree.getOrDefault(to, 0)-1);
            degree.put(from, degree.getOrDefault(from, 0)+1);
        }
        int startNode = pairs[0][0];
        for (int key : degree.keySet()) {
            if (degree.get(key) == 1) {
                startNode = key;
            }
        }
        List<Integer> result = new ArrayList<>();
        dfs(graph, startNode, result);
        Collections.reverse(result);

        int[][] res = new int[pairs.length][2];
        for (int i = 1; i < result.size(); i++) { // 11 9 4 5 1
            res[i-1][0] = result.get(i-1);
            res[i-1][1] = result.get(i);
        }
        return res;
    }
    private void dfs(Map<Integer, Deque<Integer>> graph, int startNode, List<Integer> result) {
        Deque<Integer> queue = graph.get(startNode);
        while (queue != null && !queue.isEmpty()) {
            int next = queue.poll();
            dfs(graph, next, result);
        }
        result.add(startNode);
    }
}

/***
start: out > indegree
middle node: out = indegree
end: out < indegree


T: O(V + E)
S: O(V + E)
 */