The result always said that node with label 5 is a reference!!!!


  • 0
    A
    class Solution {
    public:
        UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
    		if(node != NULL){
    			std::vector<UndirectedGraphNode*> nodesQueue;
    			nodesQueue.push_back(node);
    			size_t curPos = 0;
    			while(curPos < nodesQueue.size()){
    				UndirectedGraphNode *curNode = nodesQueue[curPos];
    				++curPos;
    				UndirectedGraphNode *newNode = new UndirectedGraphNode(curNode -> label);
    				curNode -> neighbors.push_back(newNode); //At the first time, insert the new node to the end of the old node and just left the neighbors empty 
    				int len = curNode -> neighbors.size() - 1;
    				for(int i = 0; i < len; ++i){ //Push all the neighbors of current node to the queue
    					if(curNode -> neighbors[i] != curNode && find(nodesQueue.begin(), nodesQueue.end(), curNode -> neighbors[i]) == nodesQueue.end()){//Not a node that point to itself and is a new node
    						nodesQueue.push_back(curNode -> neighbors[i]);
    					}
    				}
    			}
    			UndirectedGraphNode *result = node -> neighbors[node -> neighbors.size() - 1]; 
    			sort(nodesQueue.begin(), nodesQueue.end());
    			curPos = 0;
    			while(curPos < nodesQueue.size()){
    				UndirectedGraphNode *curNode = nodesQueue[curPos];
    				++curPos;
    				int len = curNode -> neighbors.size() - 1;
    				UndirectedGraphNode *newNode = curNode -> neighbors[len];
    				curNode -> neighbors.erase(curNode -> neighbors.end() - 1);
    				for(int i = 0; i < len; ++i){
    					if(curNode -> neighbors[i] == curNode){
    						newNode -> neighbors.push_back(newNode);
    					}else{
    						newNode -> neighbors.push_back(curNode -> neighbors[i] -> neighbors[curNode -> neighbors[i] -> neighbors.size() - 1]);
    					}
    				}
    			}
    			return result;
    		}
    		return NULL;
        }
    };
    This is the result, it's clearly that all the clone nodes is a new node rather than a reference
    
    Clone Graph
    0(0x94180f8): 1(0x9418140)5(0x9418170)
    1(0x9418140): 2(0x9418188)5(0x9418170)
    5(0x9418170): 
    2(0x9418188): 3(0x9418128)
    3(0x9418128): 4(0x94181e0)4(0x94181e0)
    4(0x94181e0): 5(0x9418170)5(0x9418170)
    
    
    Original Graph
    0(0x9418008): 1(0x9418020)5(0x9418080)
    1(0x9418020): 2(0x9418038)5(0x9418080)
    5(0x9418080): 
    2(0x9418038): 3(0x9418050)
    3(0x9418050): 4(0x9418068)4(0x9418068)
    4(0x9418068): 5(0x9418080)5(0x9418080)

  • 2
    S
    static bool cmp(UndirectedGraphNode *A, UndirectedGraphNode *B) {
        return A->label < B->label;
    }
    
    sort(nodesQueue.begin(), nodesQueue.end(), Solution::cmp);
    

    You should sort by its label, not its point address..


  • 0
    A

    Thanks!! It works and I got AC!!


Log in to reply
 

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