Clone Graph

1package pkg5leetcode.blind75;2 3/*4 * Clone Graph | LC 1335 * APPROACH: BFS/DFS with HashMap old->clone node.6 * COMPLEXITY: Time O(V+E), Space O(V)7 */8import java.util.*;9 10public class blind75_LC133CloneGraph {11    static class Node {12        int val;13        List<Node> neighbors = new ArrayList<>();14        Node(int val) { this.val = val; }15    }16 17    static Node cloneGraph(Node node) {18        if (node == null) return null;19        Map<Node, Node> map = new HashMap<>();20        Deque<Node> q = new ArrayDeque<>();21        map.put(node, new Node(node.val));22        q.add(node);23        while (!q.isEmpty()) {24            Node cur = q.poll();25            for (Node nb : cur.neighbors) {26                if (!map.containsKey(nb)) {27                    map.put(nb, new Node(nb.val));28                    q.add(nb);29                }30                map.get(cur).neighbors.add(map.get(nb));31            }32        }33        return map.get(node);34    }35 36    public static void main(String[] args) {37        Node n1 = new Node(1), n2 = new Node(2);38        n1.neighbors.add(n2); n2.neighbors.add(n1);39        Node c = cloneGraph(n1);40        check(c.val == 1 && c.neighbors.size() == 1, "case1");41        check(c.neighbors.get(0).val == 2 && c != n1, "case2");42        System.out.println("all tests passed");43    }44 45    static void check(boolean cond, String name) {46        if (!cond) throw new AssertionError("FAILED: " + name);47        System.out.println("  PASS " + name);48    }49}