# I believe undirected graph neighbor list should always contain each other

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

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

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

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

• 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).

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

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

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