javadfs twin clone

  • 0

    The idea is let every node have a twin. And we'll connect the twin together during dfs.
    Further improve: use Integer to be the key in Set and Map.

    private Set<UndirectedGraphNode> visited = new HashSet<>();
    private Map<UndirectedGraphNode, UndirectedGraphNode> bundle = new HashMap<>();
        public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
            if (null == node) return null;
            return bundle.get(node);
        private UndirectedGraphNode getTwin(UndirectedGraphNode v) {
            UndirectedGraphNode twin = null;
            if (!bundle.containsKey(v))  {
                twin = new UndirectedGraphNode(v.label);
                bundle.put(v, twin);
            else twin = bundle.get(v);
            return twin;
        private void dfs(UndirectedGraphNode v) {
            UndirectedGraphNode vTwin = getTwin(v);
            for (UndirectedGraphNode u : v.neighbors) {
                if (!visited.contains(u)) dfs(u);

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.