leetcode 133. Clone Graph-蒲公英云

leetcode 133. Clone Graph

Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

struct UndirectedGraphNode {
int label;
vector neighbors;
UndirectedGraphNode(int x) : label(x) {};
};

遍历即可

class Solution {
public:
    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
        if (node == NULL)
            return NULL;
        vector<UndirectedGraphNode*>que,nodelist,newnonelist;
        que.push_back(node); nodelist.push_back(node);
        while (!que.empty())
        {
            vector<UndirectedGraphNode*>newque;
            for (int i = 0; i < que.size(); i++)
                for (int j = 0; j < que[i]->neighbors.size(); j++)
                {
                    if (find(nodelist.begin(), nodelist.end(), que[i]->neighbors[j]) == nodelist.end())
                    {
                        nodelist.push_back(que[i]->neighbors[j]);
                        newque.push_back(que[i]->neighbors[j]);
                    }
                }
            que = newque;
        }
        for (int i = 0; i < nodelist.size(); i++)
        {
            UndirectedGraphNode*n = new UndirectedGraphNode(nodelist[i]->label);
            newnonelist.push_back(n);
        }
        for (int i = 0; i < nodelist.size(); i++)
        {
            newnonelist[i]->neighbors.clear();
            for (int j = 0; j < nodelist[i]->neighbors.size(); j++)
            {
                int index = find(nodelist.begin(), nodelist.end(), nodelist[i]->neighbors[j]) - nodelist.begin();
                newnonelist[i]->neighbors.push_back(newnonelist[index]);
            }
        }
        return newnonelist[0];
    }
};