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

// 圖節點定義
struct Node {
    int val;
    int numNeighbors;
    struct Node** neighbors;
};

// 哈希表節點定義（用於存儲原節點→克隆節點的映射）
typedef struct HashNode {
    struct Node* key;        // 原節點指針
    struct Node* value;      // 克隆節點指針
    struct HashNode* next;   // 鏈表下一個節點
} HashNode;

// 哈希表定義
#define HASH_SIZE 1009       // 哈希表大小（質數，減少衝突）
typedef struct {
    HashNode* table[HASH_SIZE];
} HashMap;

// 哈希函數：將指針轉換為整數，取模
static int hash_func(struct Node* key) {
    return (unsigned long)key % HASH_SIZE;
}

// 初始化哈希表
HashMap* hash_map_init() {
    HashMap* map = (HashMap*)malloc(sizeof(HashMap));
    memset(map->table, 0, sizeof(map->table));
    return map;
}

// 哈希表存入鍵值對
void hash_map_put(HashMap* map, struct Node* key, struct Node* value) {
    int idx = hash_func(key);
    HashNode* node = (HashNode*)malloc(sizeof(HashNode));
    node->key = key;
    node->value = value;
    node->next = map->table[idx];  // 頭插法
    map->table[idx] = node;
}

// 哈希表查詢鍵對應的值
struct Node* hash_map_get(HashMap* map, struct Node* key) {
    int idx = hash_func(key);
    HashNode* cur = map->table[idx];
    while (cur) {
        if (cur->key == key) {
            return cur->value;
        }
        cur = cur->next;
    }
    return NULL;
}

// 釋放哈希表內存
void hash_map_free(HashMap* map) {
    for (int i = 0; i < HASH_SIZE; i++) {
        HashNode* cur = map->table[i];
        while (cur) {
            HashNode* tmp = cur;
            cur = cur->next;
            free(tmp);
        }
    }
    free(map);
}

// 創建新節點（初始化值和鄰居數組）
struct Node* create_node(int val) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->val = val;
    node->numNeighbors = 0;
    node->neighbors = NULL;
    return node;
}

// 遞歸克隆節點（核心DFS邏輯）
struct Node* dfs_clone(struct Node* node, HashMap* map) {
    // 邊界條件：節點為空
    if (node == NULL) return NULL;
    
    // 已克隆過，直接返回
    struct Node* cloned = hash_map_get(map, node);
    if (cloned != NULL) return cloned;
    
    // 創建當前節點的克隆
    cloned = create_node(node->val);
    hash_map_put(map, node, cloned);  // 先存入映射，避免循環引用
    
    // 克隆所有鄰居
    cloned->numNeighbors = node->numNeighbors;
    if (node->numNeighbors > 0) {
        cloned->neighbors = (struct Node**)malloc(sizeof(struct Node*) * node->numNeighbors);
        for (int i = 0; i < node->numNeighbors; i++) {
            // 遞歸克隆鄰居節點
            cloned->neighbors[i] = dfs_clone(node->neighbors[i], map);
        }
    }
    
    return cloned;
}

// 克隆圖主函數
struct Node* cloneGraph(struct Node* node) {
    // 初始化哈希表
    HashMap* map = hash_map_init();
    // DFS克隆
    struct Node* res = dfs_clone(node, map);
    // 釋放哈希表（避免內存泄漏）
    hash_map_free(map);
    return res;
}

// 輔助函數：釋放圖的內存（測試用）
void free_graph(struct Node* node, HashMap* visited) {
    if (node == NULL) return;
    // 避免重複釋放
    if (hash_map_get(visited, node) != NULL) return;
    hash_map_put(visited, node, node);
    
    // 釋放鄰居數組
    if (node->neighbors != NULL) {
        for (int i = 0; i < node->numNeighbors; i++) {
            free_graph(node->neighbors[i], visited);
        }
        free(node->neighbors);
    }
    free(node);
}

int main() {
    // 構建原圖：1→2、4；2→1、3；3→2、4；4→1、3
    struct Node* n1 = create_node(1);
    struct Node* n2 = create_node(2);
    struct Node* n3 = create_node(3);
    struct Node* n4 = create_node(4);
    
    n1->numNeighbors = 2;
    n1->neighbors = (struct Node**)malloc(sizeof(struct Node*) * 2);
    n1->neighbors[0] = n2;
    n1->neighbors[1] = n4;
    
    n2->numNeighbors = 2;
    n2->neighbors = (struct Node**)malloc(sizeof(struct Node*) * 2);
    n2->neighbors[0] = n1;
    n2->neighbors[1] = n3;
    
    n3->numNeighbors = 2;
    n3->neighbors = (struct Node**)malloc(sizeof(struct Node*) * 2);
    n3->neighbors[0] = n2;
    n3->neighbors[1] = n4;
    
    n4->numNeighbors = 2;
    n4->neighbors = (struct Node**)malloc(sizeof(struct Node*) * 2);
    n4->neighbors[0] = n1;
    n4->neighbors[1] = n3;
    
    // 克隆圖
    struct Node* cloned = cloneGraph(n1);
    
    // 驗證克隆結果（輸出克隆節點1的鄰居值）
    printf("克隆節點1的鄰居值：");
    for (int i = 0; i < cloned->numNeighbors; i++) {
        printf("%d ", cloned->neighbors[i]->val);
    }
    printf("\n");  // 應輸出：2 4
    
    // 釋放原圖和克隆圖內存
    HashMap* visited1 = hash_map_init();
    free_graph(n1, visited1);
    hash_map_free(visited1);
    
    HashMap* visited2 = hash_map_init();
    free_graph(cloned, visited2);
    hash_map_free(visited2);
    
    return 0;
}