blob: b47c9e8d5006107cc60ca6e6bc0e7132d51cf7e8 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
// 133. Clone Graph
#include <stdbool.h>
#include <stdlib.h>
// given reference of a node in a connected undirected graph. return a deep copy
// (clone) of the graph. each node in the graph contains a value (int) and a
// list (list[node]).
struct Node {
int val;
int numNeighbors;
struct Node **neighbors;
};
struct Node *process(struct Node *s, bool *hash, struct Node **data) {
if (hash[s->val])
return data[s->val];
struct Node *root = malloc(sizeof(struct Node));
root->val = s->val;
hash[s->val] = true;
data[s->val] = root;
root->numNeighbors = s->numNeighbors;
root->neighbors = malloc(s->numNeighbors * sizeof(struct Node *));
for (int i = 0; i < s->numNeighbors; i++)
root->neighbors[i] = process(s->neighbors[i], hash, data);
return root;
}
struct Node *cloneGraph(struct Node *s) {
if (s == NULL)
return NULL;
bool *hash = calloc(101, sizeof(int));
struct Node **data = malloc(101 * sizeof(struct Node *));
return process(s, hash, data);
}
|