題目：

題解：

struct Node** visited;
int* state;  //數組存放結點狀態 0：結點未創建 1：僅創建結點 2：結點已創建并已填入所有內容void bfs(struct Node* s) {if (visited[s->val] && state[s->val] == 2) {return;}struct Node* neighbor;if (visited[s->val]) {neighbor = visited[s->val];neighbor->val = s->val;neighbor->numNeighbors = s->numNeighbors;neighbor->neighbors = (struct Node**)malloc(sizeof(struct Node*) * neighbor->numNeighbors);} else {// 如果沒有被訪問過，就克隆并存儲在哈希表中neighbor = (struct Node*)malloc(sizeof(struct Node));neighbor->val = s->val;neighbor->numNeighbors = s->numNeighbors;neighbor->neighbors = (struct Node**)malloc(sizeof(struct Node*) * neighbor->numNeighbors);visited[s->val] = neighbor;}for (int i = 0; i < neighbor->numNeighbors; i++) {if (visited[s->neighbors[i]->val]) {neighbor->neighbors[i] = visited[s->neighbors[i]->val];} else {visited[s->neighbors[i]->val] = (struct Node*)malloc(sizeof(struct Node));state[s->neighbors[i]->val] = 1;neighbor->neighbors[i] = visited[s->neighbors[i]->val];}}state[neighbor->val] = 2;
}struct Node* cloneGraph(struct Node* s) {if (s == NULL) {return NULL;}// 將題目給定的節點添加到隊列struct Node *QUEUE[101], *p;int head = -1, eneighbor = -1, i, flag[101];visited = (struct Node**)malloc(sizeof(struct Node*) * 101);memset(visited, 0, sizeof(struct Node*) * 101);state = (int*)malloc(sizeof(int) * 101);memset(state, 0, sizeof(int) * 101);memset(flag, 0, sizeof(int) * 101);// 克隆第一個節點并存儲到哈希表中QUEUE[++eneighbor] = s;// 廣度優先搜索while (head != eneighbor) {// 取出隊列的頭節點p = QUEUE[++head];// 遍歷該節點的鄰居bfs(p);for (i = 0; i < p->numNeighbors; i++) {if (!flag[p->neighbors[i]->val]) {// 將鄰居節點加入隊列中QUEUE[++eneighbor] = p->neighbors[i];flag[p->neighbors[i]->val] = 1;}}}return visited[s->val];
}