aboutsummaryrefslogtreecommitdiff
path: root/clone_graph.c
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);
}