DSA-096 · Register a fresh copy by original identity before traversing its edges

Clone Graph

Advanced · Java 21 · Version 1 · editorial draft

Java reference and baseline verified on JDK 21: 4148 deterministic checks. Learner drafts are not executed.

Understand the problem

Deep-copy the graph reachable from a root object, preserving every node value and every ordered neighbor occurrence, including cycles, self-loops and parallel edges.

Node has a final int value and a final mutable nonnull neighbor List. Reachable inputs are finite with at most 100,000 nodes and 200,000 neighbor occurrences; entries are nonnull. These structural/size bounds are preconditions. Edges may be directed; ordinary undirected graphs are a supported special case.
Values may repeat and span the full int domain. Object identity, not value, determines a vertex. Preserve the exact neighbor-list order and multiplicity: two parallel occurrences must become two references to the same corresponding copied neighbor.
Return null for null root. Otherwise return a fresh root and fresh reachable node/list objects, with no source/output aliases and no mutation of original values or lists. Copy only the reachable component; unrelated objects in an example adapter are not part of the input reachability graph.

Examples

Input: values=[7,7,9], edges=[[0,1,1],[2],[0]], root=0
Output: three fresh nodes with the same ordered edge lists
Root self-loop points to its own copy; both parallel edges point to the one copy of node 1, despite repeated value 7.
Input: values=[1,2,1,3], edges=[[1],[0],[2,3],[]], root=2
Output: copies of original nodes 2 and 3 only
The disconnected 0↔1 component must not be copied.

Before you start

Reference identity, cycles and visited ownership
BFS discovery maps and deep-copy graph isomorphism

Recognize the structure

Copying a graph requires a source-identity-to-copy relation. Allocate/register a vertex before following its outgoing edges so an edge back to it can reuse that copy instead of recursing forever or duplicating ownership.

Try before revealing

Hint 1

What should a back edge point to while a graph is being constructed?

Hint 2

You need one registered copy per original object before exploring its edges.

Hint 3

Traverse originals, allocate missing neighbor copies, and append mapped references for every list slot.

Derive the solution

Reveal the baseline, optimized reasoning, and Java code

Allocate all reachable vertices, then wire all edges

First traverse reachable originals with an identity map, allocating a copy for each and retaining an originals list. In a second pass, append every mapped neighbor in original order. This is already O(V+E); the one-pass method wires edges during BFS and avoids the separate originals pass/list, while preserving the same fundamental ownership map.

Improve the baseline

Register the root before scheduling

Put root→new Node(root.value) in IdentityHashMap and enqueue root. A self-loop encountered immediately now resolves to the existing fresh root.

Discover missing identities, not values

For each neighbor occurrence, allocate and enqueue only when that original object is absent from the map. Equal values never collapse distinct nodes.

Append every occurrence in order

Append the mapped neighbor for every list slot, whether the mapping was new or already present. Do not deduplicate adjacency lists or sort them. Return only after all source expansions complete.

Why it is correct

Partial isomorphism invariant

Every discovered original identity has exactly one fresh copy with its value. No copy is reused for another original, and source and copy allocations are disjoint.

Safe cyclic wiring

Registration occurs before enqueue/edge expansion. Back edges, self-loops and repeated occurrences therefore resolve to the same existing copy without creating another traversal owner.

Complete ordered copy

Every reachable original is discovered along a root path and expanded once. Processing all of its neighbor slots appends exactly the corresponding ordered copied references; no other reachable copy or edge is introduced.

Complete Java reference and baseline

Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.

import java.util.*;
public final class Solution {
    public static final class Node {
        public final int value;
        public final List<Node> neighbors=new ArrayList<>();
        public Node(int value){this.value=value;}
    }
    public static Node cloneGraph(Node root) {
        if(root==null)return null;
        IdentityHashMap<Node,Node> copies=new IdentityHashMap<>();ArrayDeque<Node> queue=new ArrayDeque<>();
        copies.put(root,new Node(root.value));queue.addLast(root);
        while(!queue.isEmpty()) {
            Node source=queue.removeFirst(),copy=copies.get(source);
            for(Node neighbor:source.neighbors) {
                if(!copies.containsKey(neighbor)){copies.put(neighbor,new Node(neighbor.value));queue.addLast(neighbor);}
                copy.neighbors.add(copies.get(neighbor));
            }
        }
        return copies.get(root);
    }
    public static Node baseline(Node root) {
        if(root==null)return null;
        IdentityHashMap<Node,Node> copies=new IdentityHashMap<>();List<Node> originals=new ArrayList<>();ArrayDeque<Node> stack=new ArrayDeque<>();
        copies.put(root,new Node(root.value));stack.push(root);
        while(!stack.isEmpty()){Node node=stack.pop();originals.add(node);for(Node neighbor:node.neighbors)if(!copies.containsKey(neighbor)){copies.put(neighbor,new Node(neighbor.value));stack.push(neighbor);}}
        for(Node node:originals)for(Node neighbor:node.neighbors)copies.get(node).neighbors.add(copies.get(neighbor));
        return copies.get(root);
    }
}

Read the meaningful blocks

IdentityHashMap states the key semantics

A value-keyed map fails on repeated labels. Identity semantics remain deliberate even if Node later gains value-based equals/hashCode.

Neighbor lists must also be fresh

Fresh nodes pointing to source lists are still shallow copies. Each constructor creates its own mutable list.

Count edge occurrences in complexity

Parallel entries each require an append and remain observable. E counts list slots, not only distinct pairs.

Complexity

For V reachable nodes and E reachable neighbor occurrences, main time is O(V+E) expected under the identity-map model. Auxiliary map/queue storage is O(V); returned nodes and neighbor lists require O(V+E) output storage. Null input takes constant work.

The two-pass baseline has the same asymptotic time and auxiliary order, plus an explicit O(V) originals list. Both implementations are iterative and support long cyclic/chain inputs without recursive-stack dependence.

Exact-state walkthroughs

Reveal normal and boundary traces

Self-loop, duplicate values, and parallel occurrences

Input: {"values":[7,7,9],"neighbors":[[0,1,1],[2],[0]],"start":0} · Fresh clone graph view: {"root":"C0","nodes":[{"id":"C0","value":7,"neighbors":["C0","C1","C1"]},{"id":"C1","value":7,"neighbors":["C2"]},{"id":"C2","value":9,"neighbors":["C0"]}]}

Step 1 of 10: Register a fresh root copy before scheduling its edges.

The identity map is the source-to-clone ownership relation; its record order here is discovery order, not IdentityHashMap iteration.

Graph clone — identity mapping and ordered neighbor occurrences

Phase: seed.

Original objects

G0: 7ordered edges: 0: G0; 1: G1; 2: G1
G1: 7ordered edges: 0: G2
G2: 9ordered edges: 0: G0

Fresh clone objects

C0: 7ordered edges: (none)

Source → clone ownership — discovery order

G0 → C0

Originals waiting to expand — front at left

G and C identify different objects even when their values match. Each adjacency list preserves occurrence order, parallel references, and self-loops. An original card without a mapping is unreachable or undiscovered. Clone lists are partial until construction finishes.

The exact state table and static walkthrough below provide the same information without relying on color.

State after this step
Variable	Value
originals	`[{"id":"G0","value":7,"neighbors":["G0","G1","G1"]},{"id":"G1","value":7,"neighbors":["G2"]},{"id":"G2","value":9,"neighbors":["G0"]}]`
copies	`[{"id":"C0","value":7,"neighbors":[]}]`
mapping	`[{"original":"G0","clone":"C0"}]`
queue	`["G0"]`
phase	`"seed"`
current	`null`

See the affected Java block

 1 import java.util.*;
 2 public final class Solution {
 3     public static final class Node {
 4         public final int value;
 5         public final List<Node> neighbors=new ArrayList<>();
 6         public Node(int value){this.value=value;}
 7     }
 8     public static Node cloneGraph(Node root) {
 9         if(root==null)return null;
10         IdentityHashMap<Node,Node> copies=new IdentityHashMap<>();ArrayDeque<Node> queue=new ArrayDeque<>();
11         copies.put(root,new Node(root.value));queue.addLast(root);
12         while(!queue.isEmpty()) {
13             Node source=queue.removeFirst(),copy=copies.get(source);
14             for(Node neighbor:source.neighbors) {
15                 if(!copies.containsKey(neighbor)){copies.put(neighbor,new Node(neighbor.value));queue.addLast(neighbor);}
16                 copy.neighbors.add(copies.get(neighbor));
17             }
18         }
19         return copies.get(root);
20     }
21     public static Node baseline(Node root) {
22         if(root==null)return null;
23         IdentityHashMap<Node,Node> copies=new IdentityHashMap<>();List<Node> originals=new ArrayList<>();ArrayDeque<Node> stack=new ArrayDeque<>();
24         copies.put(root,new Node(root.value));stack.push(root);
25         while(!stack.isEmpty()){Node node=stack.pop();originals.add(node);for(Node neighbor:node.neighbors)if(!copies.containsKey(neighbor)){copies.put(neighbor,new Node(neighbor.value));stack.push(neighbor);}}
26         for(Node node:originals)for(Node neighbor:node.neighbors)copies.get(node).neighbors.add(copies.get(neighbor));
27         return copies.get(root);
28     }
29 }
30

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Register a fresh root copy before scheduling its edges.
The identity map is the source-to-clone ownership relation; its record order here is discovery order, not IdentityHashMap iteration.
originals
[{"id":"G0","value":7,"neighbors":["G0","G1","G1"]},{"id":"G1","value":7,"neighbors":["G2"]},{"id":"G2","value":9,"neighbors":["G0"]}]
copies
[{"id":"C0","value":7,"neighbors":[]}]
mapping
[{"original":"G0","clone":"C0"}]
queue
["G0"]
phase
"seed"
current
null
Expand one original adjacency list in its exact stored order.
Each discovered original identity is expanded once. Partially filled clone lists are local construction state, not returned output yet.
originals
[{"id":"G0","value":7,"neighbors":["G0","G1","G1"]},{"id":"G1","value":7,"neighbors":["G2"]},{"id":"G2","value":9,"neighbors":["G0"]}]
copies
[{"id":"C0","value":7,"neighbors":[]}]
mapping
[{"original":"G0","clone":"C0"}]
queue
[]
phase
"expand"
current
"G0"
Append this neighbor occurrence, reusing any registered copy.
Repeated edges append repeated references; self-loops and cycles point to the same registered clone, never a value-keyed replacement.
originals
[{"id":"G0","value":7,"neighbors":["G0","G1","G1"]},{"id":"G1","value":7,"neighbors":["G2"]},{"id":"G2","value":9,"neighbors":["G0"]}]
copies
[{"id":"C0","value":7,"neighbors":["C0"]}]
mapping
[{"original":"G0","clone":"C0"}]
queue
[]
phase
"edge"
current
"G0"
neighbor
"G0"
edgeIndex
0
created
false
Append this neighbor occurrence, reusing any registered copy.
Repeated edges append repeated references; self-loops and cycles point to the same registered clone, never a value-keyed replacement.
originals
[{"id":"G0","value":7,"neighbors":["G0","G1","G1"]},{"id":"G1","value":7,"neighbors":["G2"]},{"id":"G2","value":9,"neighbors":["G0"]}]
copies
[{"id":"C0","value":7,"neighbors":["C0","C1"]},{"id":"C1","value":7,"neighbors":[]}]
mapping
[{"original":"G0","clone":"C0"},{"original":"G1","clone":"C1"}]
queue
["G1"]
phase
"edge"
current
"G0"
neighbor
"G1"
edgeIndex
1
created
true
Append this neighbor occurrence, reusing any registered copy.
Repeated edges append repeated references; self-loops and cycles point to the same registered clone, never a value-keyed replacement.
originals
[{"id":"G0","value":7,"neighbors":["G0","G1","G1"]},{"id":"G1","value":7,"neighbors":["G2"]},{"id":"G2","value":9,"neighbors":["G0"]}]
copies
[{"id":"C0","value":7,"neighbors":["C0","C1","C1"]},{"id":"C1","value":7,"neighbors":[]}]
mapping
[{"original":"G0","clone":"C0"},{"original":"G1","clone":"C1"}]
queue
["G1"]
phase
"edge"
current
"G0"
neighbor
"G1"
edgeIndex
2
created
false
Expand one original adjacency list in its exact stored order.
Each discovered original identity is expanded once. Partially filled clone lists are local construction state, not returned output yet.
originals
[{"id":"G0","value":7,"neighbors":["G0","G1","G1"]},{"id":"G1","value":7,"neighbors":["G2"]},{"id":"G2","value":9,"neighbors":["G0"]}]
copies
[{"id":"C0","value":7,"neighbors":["C0","C1","C1"]},{"id":"C1","value":7,"neighbors":[]}]
mapping
[{"original":"G0","clone":"C0"},{"original":"G1","clone":"C1"}]
queue
[]
phase
"expand"
current
"G1"
Append this neighbor occurrence, reusing any registered copy.
Repeated edges append repeated references; self-loops and cycles point to the same registered clone, never a value-keyed replacement.
originals
[{"id":"G0","value":7,"neighbors":["G0","G1","G1"]},{"id":"G1","value":7,"neighbors":["G2"]},{"id":"G2","value":9,"neighbors":["G0"]}]
copies
[{"id":"C0","value":7,"neighbors":["C0","C1","C1"]},{"id":"C1","value":7,"neighbors":["C2"]},{"id":"C2","value":9,"neighbors":[]}]
mapping
[{"original":"G0","clone":"C0"},{"original":"G1","clone":"C1"},{"original":"G2","clone":"C2"}]
queue
["G2"]
phase
"edge"
current
"G1"
neighbor
"G2"
edgeIndex
0
created
true
Expand one original adjacency list in its exact stored order.
Each discovered original identity is expanded once. Partially filled clone lists are local construction state, not returned output yet.
originals
[{"id":"G0","value":7,"neighbors":["G0","G1","G1"]},{"id":"G1","value":7,"neighbors":["G2"]},{"id":"G2","value":9,"neighbors":["G0"]}]
copies
[{"id":"C0","value":7,"neighbors":["C0","C1","C1"]},{"id":"C1","value":7,"neighbors":["C2"]},{"id":"C2","value":9,"neighbors":[]}]
mapping
[{"original":"G0","clone":"C0"},{"original":"G1","clone":"C1"},{"original":"G2","clone":"C2"}]
queue
[]
phase
"expand"
current
"G2"
Append this neighbor occurrence, reusing any registered copy.
Repeated edges append repeated references; self-loops and cycles point to the same registered clone, never a value-keyed replacement.
originals
[{"id":"G0","value":7,"neighbors":["G0","G1","G1"]},{"id":"G1","value":7,"neighbors":["G2"]},{"id":"G2","value":9,"neighbors":["G0"]}]
copies
[{"id":"C0","value":7,"neighbors":["C0","C1","C1"]},{"id":"C1","value":7,"neighbors":["C2"]},{"id":"C2","value":9,"neighbors":["C0"]}]
mapping
[{"original":"G0","clone":"C0"},{"original":"G1","clone":"C1"},{"original":"G2","clone":"C2"}]
queue
[]
phase
"edge"
current
"G2"
neighbor
"G0"
edgeIndex
0
created
false
Return the documented value, changed-grid view, fresh result, or cloned graph view.
Coordinates and object identities follow the problem-specific contract. Discovery histories are teaching views, not additional Java workspace.
result
{"root":"C0","nodes":[{"id":"C0","value":7,"neighbors":["C0","C1","C1"]},{"id":"C1","value":7,"neighbors":["C2"]},{"id":"C2","value":9,"neighbors":["C0"]}]}

Copy only the reachable component

Input: {"values":[1,2,1,3],"neighbors":[[1],[0],[2,3],[]],"start":2} · Fresh clone graph view: {"root":"C0","nodes":[{"id":"C0","value":1,"neighbors":["C0","C1"]},{"id":"C1","value":3,"neighbors":[]}]}

Step 1 of 6: Register a fresh root copy before scheduling its edges.

The identity map is the source-to-clone ownership relation; its record order here is discovery order, not IdentityHashMap iteration.

Graph clone — identity mapping and ordered neighbor occurrences

Phase: seed.

Original objects

G0: 1ordered edges: 0: G1
G1: 2ordered edges: 0: G0
G2: 1ordered edges: 0: G2; 1: G3
G3: 3ordered edges: (none)

Fresh clone objects

C0: 1ordered edges: (none)

Source → clone ownership — discovery order

G2 → C0

Originals waiting to expand — front at left

The exact state table and static walkthrough below provide the same information without relying on color.

State after this step
Variable	Value
originals	`[{"id":"G0","value":1,"neighbors":["G1"]},{"id":"G1","value":2,"neighbors":["G0"]},{"id":"G2","value":1,"neighbors":["G2","G3"]},{"id":"G3","value":3,"neighbors":[]}]`
copies	`[{"id":"C0","value":1,"neighbors":[]}]`
mapping	`[{"original":"G2","clone":"C0"}]`
queue	`["G2"]`
phase	`"seed"`
current	`null`

See the affected Java block

 1 import java.util.*;
 2 public final class Solution {
 3     public static final class Node {
 4         public final int value;
 5         public final List<Node> neighbors=new ArrayList<>();
 6         public Node(int value){this.value=value;}
 7     }
 8     public static Node cloneGraph(Node root) {
 9         if(root==null)return null;
10         IdentityHashMap<Node,Node> copies=new IdentityHashMap<>();ArrayDeque<Node> queue=new ArrayDeque<>();
11         copies.put(root,new Node(root.value));queue.addLast(root);
12         while(!queue.isEmpty()) {
13             Node source=queue.removeFirst(),copy=copies.get(source);
14             for(Node neighbor:source.neighbors) {
15                 if(!copies.containsKey(neighbor)){copies.put(neighbor,new Node(neighbor.value));queue.addLast(neighbor);}
16                 copy.neighbors.add(copies.get(neighbor));
17             }
18         }
19         return copies.get(root);
20     }
21     public static Node baseline(Node root) {
22         if(root==null)return null;
23         IdentityHashMap<Node,Node> copies=new IdentityHashMap<>();List<Node> originals=new ArrayList<>();ArrayDeque<Node> stack=new ArrayDeque<>();
24         copies.put(root,new Node(root.value));stack.push(root);
25         while(!stack.isEmpty()){Node node=stack.pop();originals.add(node);for(Node neighbor:node.neighbors)if(!copies.containsKey(neighbor)){copies.put(neighbor,new Node(neighbor.value));stack.push(neighbor);}}
26         for(Node node:originals)for(Node neighbor:node.neighbors)copies.get(node).neighbors.add(copies.get(neighbor));
27         return copies.get(root);
28     }
29 }
30

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Register a fresh root copy before scheduling its edges.
The identity map is the source-to-clone ownership relation; its record order here is discovery order, not IdentityHashMap iteration.
originals
[{"id":"G0","value":1,"neighbors":["G1"]},{"id":"G1","value":2,"neighbors":["G0"]},{"id":"G2","value":1,"neighbors":["G2","G3"]},{"id":"G3","value":3,"neighbors":[]}]
copies
[{"id":"C0","value":1,"neighbors":[]}]
mapping
[{"original":"G2","clone":"C0"}]
queue
["G2"]
phase
"seed"
current
null
Expand one original adjacency list in its exact stored order.
Each discovered original identity is expanded once. Partially filled clone lists are local construction state, not returned output yet.
originals
[{"id":"G0","value":1,"neighbors":["G1"]},{"id":"G1","value":2,"neighbors":["G0"]},{"id":"G2","value":1,"neighbors":["G2","G3"]},{"id":"G3","value":3,"neighbors":[]}]
copies
[{"id":"C0","value":1,"neighbors":[]}]
mapping
[{"original":"G2","clone":"C0"}]
queue
[]
phase
"expand"
current
"G2"
Append this neighbor occurrence, reusing any registered copy.
Repeated edges append repeated references; self-loops and cycles point to the same registered clone, never a value-keyed replacement.
originals
[{"id":"G0","value":1,"neighbors":["G1"]},{"id":"G1","value":2,"neighbors":["G0"]},{"id":"G2","value":1,"neighbors":["G2","G3"]},{"id":"G3","value":3,"neighbors":[]}]
copies
[{"id":"C0","value":1,"neighbors":["C0"]}]
mapping
[{"original":"G2","clone":"C0"}]
queue
[]
phase
"edge"
current
"G2"
neighbor
"G2"
edgeIndex
0
created
false
Append this neighbor occurrence, reusing any registered copy.
Repeated edges append repeated references; self-loops and cycles point to the same registered clone, never a value-keyed replacement.
originals
[{"id":"G0","value":1,"neighbors":["G1"]},{"id":"G1","value":2,"neighbors":["G0"]},{"id":"G2","value":1,"neighbors":["G2","G3"]},{"id":"G3","value":3,"neighbors":[]}]
copies
[{"id":"C0","value":1,"neighbors":["C0","C1"]},{"id":"C1","value":3,"neighbors":[]}]
mapping
[{"original":"G2","clone":"C0"},{"original":"G3","clone":"C1"}]
queue
["G3"]
phase
"edge"
current
"G2"
neighbor
"G3"
edgeIndex
1
created
true
Expand one original adjacency list in its exact stored order.
Each discovered original identity is expanded once. Partially filled clone lists are local construction state, not returned output yet.
originals
[{"id":"G0","value":1,"neighbors":["G1"]},{"id":"G1","value":2,"neighbors":["G0"]},{"id":"G2","value":1,"neighbors":["G2","G3"]},{"id":"G3","value":3,"neighbors":[]}]
copies
[{"id":"C0","value":1,"neighbors":["C0","C1"]},{"id":"C1","value":3,"neighbors":[]}]
mapping
[{"original":"G2","clone":"C0"},{"original":"G3","clone":"C1"}]
queue
[]
phase
"expand"
current
"G3"
Return the documented value, changed-grid view, fresh result, or cloned graph view.
Coordinates and object identities follow the problem-specific contract. Discovery histories are teaching views, not additional Java workspace.
result
{"root":"C0","nodes":[{"id":"C0","value":1,"neighbors":["C0","C1"]},{"id":"C1","value":3,"neighbors":[]}]}

Null root ignores unrelated adapter objects

Input: {"values":[1],"neighbors":[[0]],"start":null} · Fresh clone graph view: null

Step 1 of 2: An absent root has no reachable component to copy.

Node values do not identify objects. Disconnected source nodes are not copied merely because they appear in the adapter.

Graph clone — identity mapping and ordered neighbor occurrences

Phase: empty.

Original objects

G0: 1ordered edges: 0: G0

Fresh clone objects

Source → clone ownership — discovery order

Empty.

Originals waiting to expand — front at left

Empty.

The exact state table and static walkthrough below provide the same information without relying on color.

State after this step
Variable	Value
originals	`[{"id":"G0","value":1,"neighbors":["G0"]}]`
copies	`[]`
mapping	`[]`
queue	`[]`
phase	`"empty"`
current	`null`

See the affected Java block

 1 import java.util.*;
 2 public final class Solution {
 3     public static final class Node {
 4         public final int value;
 5         public final List<Node> neighbors=new ArrayList<>();
 6         public Node(int value){this.value=value;}
 7     }
 8     public static Node cloneGraph(Node root) {
 9         if(root==null)return null;
10         IdentityHashMap<Node,Node> copies=new IdentityHashMap<>();ArrayDeque<Node> queue=new ArrayDeque<>();
11         copies.put(root,new Node(root.value));queue.addLast(root);
12         while(!queue.isEmpty()) {
13             Node source=queue.removeFirst(),copy=copies.get(source);
14             for(Node neighbor:source.neighbors) {
15                 if(!copies.containsKey(neighbor)){copies.put(neighbor,new Node(neighbor.value));queue.addLast(neighbor);}
16                 copy.neighbors.add(copies.get(neighbor));
17             }
18         }
19         return copies.get(root);
20     }
21     public static Node baseline(Node root) {
22         if(root==null)return null;
23         IdentityHashMap<Node,Node> copies=new IdentityHashMap<>();List<Node> originals=new ArrayList<>();ArrayDeque<Node> stack=new ArrayDeque<>();
24         copies.put(root,new Node(root.value));stack.push(root);
25         while(!stack.isEmpty()){Node node=stack.pop();originals.add(node);for(Node neighbor:node.neighbors)if(!copies.containsKey(neighbor)){copies.put(neighbor,new Node(neighbor.value));stack.push(neighbor);}}
26         for(Node node:originals)for(Node neighbor:node.neighbors)copies.get(node).neighbors.add(copies.get(neighbor));
27         return copies.get(root);
28     }
29 }
30

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

An absent root has no reachable component to copy.
Node values do not identify objects. Disconnected source nodes are not copied merely because they appear in the adapter.
originals
[{"id":"G0","value":1,"neighbors":["G0"]}]
copies
[]
mapping
[]
queue
[]
phase
"empty"
current
null
Return the documented value, changed-grid view, fresh result, or cloned graph view.
Coordinates and object identities follow the problem-specific contract. Discovery histories are teaching views, not additional Java workspace.
result
null

Test the contract

Input: Null root
Output: null
No component.
Input: Repeated values and a self-loop
Output: distinct copied identities with correct self-reference
Values do not identify nodes.
Input: Parallel directed edges and cycles
Output: exact occurrence order preserved
No deduplication.
Input: 100,000-node undirected chain
Output: independent isomorphic component
Explicit frontier and full identity coverage.

Common mistakes and counterexamples

Key copies by value

Counterexample: Two original 7-valued nodes can have different adjacency and must remain distinct.

Key by original reference identity.

Register after exploring neighbors

Counterexample: A self-loop or cycle reaches an unregistered object again.

Allocate and register before scheduling its edges.

Turn neighbor lists into sets

Counterexample: Parallel edges and original order disappear.

Append every original occurrence in order.

Reuse source neighbor lists

Counterexample: Editing a copy would mutate the source.

Allocate independent lists for every copied node.

Follow-ups

Copy an entire disconnected graph.

Accept an explicit collection of roots/vertices and reuse one identity map across them. Define output root ordering and whether unreachable supplied vertices must appear.

Preserve edge metadata or list sharing.

Specify which objects are owned and copied. If source adjacency-list objects themselves may intentionally be shared, preserving that sharing requires a separate identity mapping for lists.

Copy while the graph changes concurrently.

A traversal does not automatically provide a consistent snapshot. Require external locking, immutable snapshots or a versioned retry protocol; do not imply this static algorithm solves concurrency.

Your Java attempt

Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.

Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.

Approach, code, and test notes (20,000 characters maximum)

No unsaved text changes · 152/20,000 characters

Self-review

Can I explain why registration must precede edge traversal?Can I check both node and neighbor-list freshness?Can I preserve multiplicity/order while preventing duplicate vertex copies?

Use the checklist to test your explanation. Checks apply to this visit.

Related foundations

Keep practicing

Open focused practice

AceYourInterviews · 2026-10-17 · Original teaching content and implementations authored for AceYourInterviews. Standard names do not imply company-frequency or external-platform equivalence claims.