I believe undirected graph neighbor list should always contain each other

  • 7

    It seems to me the input from OJ is problematic. When a and b are neighbors, b is in a's neighbor list but a is not in b's neighbor list. Under such condition only certain algorithm can generate correct output.

    I've pasted a BFS solution which is correct if a and b are put into to each other's neighbor list, but doesn't work properly under current OJ:

    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
            //key -> old node, value -> the new copy
            unordered_map<UndirectedGraphNode*, UndirectedGraphNode*> m;
            //the queue always contains old nodes that haven't been copied
            queue<UndirectedGraphNode*> q;
            while(!q.empty()) {
                UndirectedGraphNode* n = q.front();
                if(m.count(n)) continue; // if the node is already copied, continue
                // create the copy
                m[n] = new UndirectedGraphNode(n->label);
                // loop through the neighbors, if it's copied already, add the new copy to new copy's neighbor list
                for(UndirectedGraphNode* oldNei : n->neighbors) {
                    if(m.count(oldNei)) {
                        UndirectedGraphNode* newNei = m[oldNei];
                    else// if not in the map, it's not copied/visited yet
            return m[node];

    This won't pass case {-1,1#1} since 1 is neighbor of -1, but -1 is not neighbor of 1.

    If you think the above algorithm is wrong, please point it out. Otherwise I think the OJ needs to be fixed.

  • 3

    I think so. The representation of undirected graph here is really stupid. And some inputs even contain duplicates in the neighbors.

  • 1

    i have the same question. It's more like a directed graph

  • 2

    I agree with you. The input is so unusual that I got many bugs in this problem.

  • 1

    I thought maybe it's just the input representation, but I added

        if (node && node->neighbors.size())
            cout << node->neighbors[0]->neighbors.size() << endl;

    to your solution which prints "0" for input "{-1,1#1}", so yeah, that's indeed bad (there's a neighbor who doesn't have neighbors).

  • 0

    AGREE. And it's a high-freq problem... I don't know what I should write in a real interview...

  • 0

    @ArchiiiTech I agree. This problem itself is actually a directed graph. All edges in the graph are unidirectional.

Log in to reply

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