題目：133. Clone Graph

連結：https://leetcode.com/problems/clone-graph/description/

• 等級：Medium

解題思路

dfs 中的每個節點並複製它並根據其值將其儲存在映射中。 因此，當節點重新出現/存取時，請使用現有節點作為該值。 當訪問一個節點時，克隆它並將其添加到映射中並訪問其鄰居

class Solution {
    public Node cloneGraph(Node node) {
        if(node == null){
            return null;
        }
        return clone(node,new HashMap<Integer,Node>());
        
    }
    public Node clone(Node node,Map<Integer,Node> map){
        if(map.containsKey(node.val)){
            return map.get(node.val);
        }
        Node newNode = new Node(node.val);
        map.put(node.val,newNode);
        for(Node myNode : node.neighbors){
            newNode.neighbors.add(clone(myNode,map));
        }
        return newNode;
    }
}

• Time complexity: O(n)
• Space complexity: O(n)

題目：207. Course Schedule

連結：https://leetcode.com/problems/course-schedule/description/

• 等級：Medium

解題思路

如果圖中存在環，則至少有一個節點無法訪問，因為它始終具有indegree。 另一方面，如果不存在循環，則可以透過從沒有入邊的節點開始並逐一刪除其出邊來存取所有節點。 如果最後所有的節點都被訪問過，則意味著可以完成所有的課程。

class Solution {
    public boolean canFinish(int n, int[][] prerequisites) {
        List<Integer>[] adj = new List[n];
        int[] indegree = new int[n];
        List<Integer> ans = new ArrayList<>();

        for (int[] pair : prerequisites) {
            int course = pair[0];
            int prerequisite = pair[1];
            if (adj[prerequisite] == null) {
                adj[prerequisite] = new ArrayList<>();
            }
            adj[prerequisite].add(course);
            indegree[course]++;
        }

        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (indegree[i] == 0) {
                queue.offer(i);
            }
        }

        while (!queue.isEmpty()) {
            int current = queue.poll();
            ans.add(current);

            if (adj[current] != null) {
                for (int next : adj[current]) {
                    indegree[next]--;
                    if (indegree[next] == 0) {
                        queue.offer(next);
                    }
                }
            }
        }

        return ans.size() == n;
    }
}

• Time complexity: O(n)
• Space complexity: O(n)