Clone a Graph

#include <stdio.h>
#include <stdlib.h>

#define MAX 100

// A node has a value and a fixed-size list of neighbor pointers.
typedef struct Node {
    int val;
    struct Node* neighbors[MAX];
    int count;
} Node;

Node* visited[MAX]; // visited[val] = copy of the node with that value (values are unique and small here)

Node* newNode(int val) {
    Node* n = (Node*)malloc(sizeof(Node));
    n->val = val;
    n->count = 0;
    return n;
}

// DFS clone using the visited table indexed by value.
Node* cloneDFS(Node* node) {
    if (node == NULL) return NULL;
    if (visited[node->val] != NULL) return visited[node->val]; // already copied

    Node* copy = newNode(node->val);
    visited[node->val] = copy; // store before visiting neighbors

    for (int i = 0; i < node->count; i++) {
        copy->neighbors[copy->count++] = cloneDFS(node->neighbors[i]);
    }
    return copy;
}

int main() {
    for (int i = 0; i < MAX; i++) visited[i] = NULL;

    // Build the graph: 1-2, 2-3, 3-4, 4-1
    Node* n1 = newNode(1);
    Node* n2 = newNode(2);
    Node* n3 = newNode(3);
    Node* n4 = newNode(4);
    n1->neighbors[n1->count++] = n2; n1->neighbors[n1->count++] = n4;
    n2->neighbors[n2->count++] = n1; n2->neighbors[n2->count++] = n3;
    n3->neighbors[n3->count++] = n2; n3->neighbors[n3->count++] = n4;
    n4->neighbors[n4->count++] = n1; n4->neighbors[n4->count++] = n3;

    Node* clone = cloneDFS(n1);

    // Print each cloned node and its neighbor values.
    for (int v = 1; v <= 4; v++) {
        Node* c = visited[v];
        printf("Node %d neighbors:", c->val);
        for (int i = 0; i < c->count; i++) printf(" %d", c->neighbors[i]->val);
        printf("\n");
    }
    printf("Original n1 == clone? %s\n", (n1 == clone) ? "yes" : "no");
    return 0;
}

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

// A node holds a value and pointers to its neighbors.
struct Node {
    int val;
    vector<Node*> neighbors;
    Node(int v) : val(v) {}
};

unordered_map<Node*, Node*> visited; // original node -> its copy

// DFS clone. Store the copy before exploring neighbors.
Node* cloneDFS(Node* node) {
    if (node == nullptr) return nullptr;
    if (visited.count(node)) return visited[node]; // already copied

    Node* copy = new Node(node->val);
    visited[node] = copy; // store first, then recurse

    for (Node* nb : node->neighbors) {
        copy->neighbors.push_back(cloneDFS(nb));
    }
    return copy;
}

int main() {
    // Build the graph: 1-2, 2-3, 3-4, 4-1
    Node* n1 = new Node(1);
    Node* n2 = new Node(2);
    Node* n3 = new Node(3);
    Node* n4 = new Node(4);
    n1->neighbors = {n2, n4};
    n2->neighbors = {n1, n3};
    n3->neighbors = {n2, n4};
    n4->neighbors = {n1, n3};

    Node* clone = cloneDFS(n1);

    // Print the cloned graph.
    for (Node* c : {visited[n1], visited[n2], visited[n3], visited[n4]}) {
        cout << "Node " << c->val << " neighbors:";
        for (Node* nb : c->neighbors) cout << " " << nb->val;
        cout << "\n";
    }
    cout << "Original n1 == clone? " << (n1 == clone ? "yes" : "no") << "\n";
    return 0;
}

import java.util.*;

public class CloneGraph {
    // A node holds a value and a list of neighbors.
    static class Node {
        int val;
        List<Node> neighbors = new ArrayList<>();
        Node(int v) { val = v; }
    }

    // original node -> its copy
    static Map<Node, Node> visited = new HashMap<>();

    // DFS clone. Put the copy in the map before visiting neighbors.
    static Node cloneDFS(Node node) {
        if (node == null) return null;
        if (visited.containsKey(node)) return visited.get(node); // already copied

        Node copy = new Node(node.val);
        visited.put(node, copy); // store first, then recurse

        for (Node nb : node.neighbors) {
            copy.neighbors.add(cloneDFS(nb));
        }
        return copy;
    }

    public static void main(String[] args) {
        // Build the graph: 1-2, 2-3, 3-4, 4-1
        Node n1 = new Node(1), n2 = new Node(2), n3 = new Node(3), n4 = new Node(4);
        n1.neighbors = new ArrayList<>(List.of(n2, n4));
        n2.neighbors = new ArrayList<>(List.of(n1, n3));
        n3.neighbors = new ArrayList<>(List.of(n2, n4));
        n4.neighbors = new ArrayList<>(List.of(n1, n3));

        Node clone = cloneDFS(n1);

        // Print the cloned graph.
        for (Node c : new Node[]{visited.get(n1), visited.get(n2), visited.get(n3), visited.get(n4)}) {
            StringBuilder line = new StringBuilder("Node " + c.val + " neighbors:");
            for (Node nb : c.neighbors) line.append(" ").append(nb.val);
            System.out.println(line.toString());
        }
        System.out.println("Original n1 == clone? " + (n1 == clone ? "yes" : "no"));
    }
}

# A node holds a value and a list of neighbors.
class Node:
    def __init__(self, val):
        self.val = val
        self.neighbors = []

# original node -> its copy
visited = {}

# DFS clone. Store the copy before visiting neighbors.
def clone_dfs(node):
    if node is None:
        return None
    if node in visited:
        return visited[node]  # already copied

    copy = Node(node.val)
    visited[node] = copy  # store first, then recurse

    for nb in node.neighbors:
        copy.neighbors.append(clone_dfs(nb))
    return copy


# Build the graph: 1-2, 2-3, 3-4, 4-1
n1, n2, n3, n4 = Node(1), Node(2), Node(3), Node(4)
n1.neighbors = [n2, n4]
n2.neighbors = [n1, n3]
n3.neighbors = [n2, n4]
n4.neighbors = [n1, n3]

clone = clone_dfs(n1)

# Print the cloned graph.
for c in (visited[n1], visited[n2], visited[n3], visited[n4]):
    neighbor_vals = " ".join(str(nb.val) for nb in c.neighbors)
    print(f"Node {c.val} neighbors: {neighbor_vals}")
print(f"Original n1 == clone? {'yes' if n1 is clone else 'no'}")

// A node holds a value and a list of neighbors.
class Node {
  constructor(val) {
    this.val = val;
    this.neighbors = [];
  }
}

// original node -> its copy
const visited = new Map();

// DFS clone. Store the copy before visiting neighbors.
function cloneDFS(node) {
  if (node === null) return null;
  if (visited.has(node)) return visited.get(node); // already copied

  const copy = new Node(node.val);
  visited.set(node, copy); // store first, then recurse

  for (const nb of node.neighbors) {
    copy.neighbors.push(cloneDFS(nb));
  }
  return copy;
}

// Build the graph: 1-2, 2-3, 3-4, 4-1
const n1 = new Node(1), n2 = new Node(2), n3 = new Node(3), n4 = new Node(4);
n1.neighbors = [n2, n4];
n2.neighbors = [n1, n3];
n3.neighbors = [n2, n4];
n4.neighbors = [n1, n3];

const clone = cloneDFS(n1);

// Print the cloned graph.
for (const c of [visited.get(n1), visited.get(n2), visited.get(n3), visited.get(n4)]) {
  const neighborVals = c.neighbors.map((nb) => nb.val).join(" ");
  console.log(`Node ${c.val} neighbors: ${neighborVals}`);
}
console.log(`Original n1 == clone? ${n1 === clone ? "yes" : "no"}`);