C, bfs, no hashmap, 16 ms


  • 0
    L

    The input is not const so you can freely modify it to help construct a clone without a hash map. I'm using a standard breadth first search. I flip the sign of the neighborsCount field to signify that I've already visited a node: negative have been visited, non-negative are the nodes yet to be added to the queue. I'm also cloning the nodes as I'm processing the nodes in the bfs algorithm and use the label field as index into the array of new nodes. After the bfs I make another pass to clone the neighbor lists and yet another pass to restore the original graph. The code is a bit long but faster than using maps.

    Note: In C++'s case you need to find another way to mark visited nodes. E.g. you could push back a sentinel NULL pointer to the end of neighbors. Also, I've found another similar no hashmap solution which uses the neighbor lists in a different way: https://discuss.leetcode.com/topic/5500/my-java-solution-with-o-n-time-without-hash-map

    // Note q means queue, qb means queue begin, the next entry's index, qe means
    // queue end, the last element's index in the queue plus one.
    struct UndirectedGraphNode *q[12345];
    struct UndirectedGraphNode *newnodes[12345];
    struct UndirectedGraphNode *cloneGraph(struct UndirectedGraphNode *graph) {
      if (graph == NULL) return NULL;
      // Traverse the graph and copy individual nodes into newnodes in the same
      // order as in the array q. Use negative neighborsCount to mark visited nodes,
      // and the label field for index into q and newnodes arrays. The newnodes copy
      // will contain the actual label value.
      int qb = 0, qe = 0;
      q[qe++] = graph;
      graph->neighborsCount = -(graph->neighborsCount + 1);
      while (qb != qe) {
        struct UndirectedGraphNode *newnode, *oldnode;
        newnode = malloc(sizeof(*newnode));
        newnodes[qb] = newnode;
        oldnode = q[qb];
        newnode->label = oldnode->label;
        oldnode->label = qb;
        int neighbors = -(oldnode->neighborsCount + 1);
        qb++;
        for (int i = 0; i < neighbors; i++) {
          struct UndirectedGraphNode *n = oldnode->neighbors[i];
          if (n->neighborsCount < 0) continue;
          q[qe++] = n;
          n->neighborsCount = -(n->neighborsCount + 1);
          if (qe >= 12345) {
            puts("Graph too large, aborting.");
            abort();
          }
        }
      }
      // Copy the neighbor info into the newnodes array and restore the
      // neighborsCount field in the original nodes.
      for (int i = 0; i < qe; i++) {
        struct UndirectedGraphNode *newnode, *oldnode;
        newnode = newnodes[i];
        oldnode = q[i];
        int neighbors = -(oldnode->neighborsCount + 1);
        oldnode->neighborsCount = neighbors;
        newnode->neighborsCount = neighbors;
        for (int j = 0; j < neighbors; j++) {
          newnode->neighbors[j] = newnodes[oldnode->neighbors[j]->label];
        }
      }
      // Now restore the label info in the old nodes.
      for (int i = 0; i < qe; i++) {
        q[i]->label = newnodes[i]->label;
      }
      return newnodes[0];
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.