clonegraph.cpp

#include <iostream>
using namespace std;

class Node {
public:
    int val;
    Node** neighbors;
    int neighborCount;

    Node(int _val) {
        val = _val;
        neighbors = new Node*[101]; // support up to 100 neighbors
        neighborCount = 0;
    }

    ~Node() {
        delete[] neighbors;
    }
};

class Solution {
public:
    Node* visited[101]; // array to map node val -> cloned node pointer

    Solution() {
        for (int i = 0; i <= 100; i++) {
            visited[i] = NULL;
        }
    }

    Node* cloneGraph(Node* node) {
        if (node == NULL) return NULL;

        if (visited[node->val] != NULL) {
            return visited[node->val];
        }

        // Create clone
        Node* cloneNode = new Node(node->val);
        visited[node->val] = cloneNode;

        // Recursively clone neighbors
        for (int i = 0; i < node->neighborCount; i++) {
            Node* neighbor = node->neighbors[i];
            Node* clonedNeighbor = cloneGraph(neighbor);
            cloneNode->neighbors[cloneNode->neighborCount++] = clonedNeighbor;
        }

        return cloneNode;
    }
};

void printGraph(Node* node, bool* printed) {
    if (node == NULL || printed[node->val]) return;

    printed[node->val] = true;
    cout << "Node " << node->val << " is connected to: ";
    for (int i = 0; i < node->neighborCount; i++) {
        cout << node->neighbors[i]->val << " ";
    }
    cout << endl;

    for (int i = 0; i < node->neighborCount; i++) {
        printGraph(node->neighbors[i], printed);
    }
}

int main() {
    // Create a small graph: 1--2, 1--3, 2--4
    Node* node1 = new Node(1);
    Node* node2 = new Node(2);
    Node* node3 = new Node(3);
    Node* node4 = new Node(4);

    node1->neighbors[node1->neighborCount++] = node2;
    node1->neighbors[node1->neighborCount++] = node3;

    node2->neighbors[node2->neighborCount++] = node1;
    node2->neighbors[node2->neighborCount++] = node4;

    node3->neighbors[node3->neighborCount++] = node1;

    node4->neighbors[node4->neighborCount++] = node2;

    // Print original graph
    bool printedOriginal[101] = {false};
    cout << "Original Graph:\n";
    printGraph(node1, printedOriginal);

    // Clone the graph
    Solution sol;
    Node* cloned = sol.cloneGraph(node1);

    // Print cloned graph
    bool printedClone[101] = {false};
    cout << "\nCloned Graph:\n";
    printGraph(cloned, printedClone);

    // Clean up original graph
    delete node1;
    delete node2;
    delete node3;
    delete node4;

    // Clean up cloned graph
    for (int i = 1; i <= 100; i++) {
        if (sol.visited[i] != NULL) {
            delete sol.visited[i];
        }
    }

    return 0;
}