I believe undirected graph neighbor list should always contain each other


  • 7
    A

    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;
            if(node)
                q.push(node);
            
            while(!q.empty()) {
                
                UndirectedGraphNode* n = q.front();
                q.pop();
                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];
                        
                        if(m[n]->neighbors.size()==n->neighbors.size())
                            continue;
                        
                        m[n]->neighbors.push_back(newNei);
                        newNei->neighbors.push_back(m[n]);
                    }
                    
                    else// if not in the map, it's not copied/visited yet
                    
                        q.push(oldNei);
                }
    
            }
            
            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

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


  • 1
    T

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


  • 2
    S

    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
    A

    @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.