leetcode 133. Clone Graph
1525 ワード
Clone an undirected graph. Each node in the graph contains a
struct UndirectedGraphNode { int label; vector neighbors; UndirectedGraphNode(int x) : label(x) {}; };
遍歴すればよい
accepted
label
and a list of its neighbors
. struct UndirectedGraphNode { int label; vector
遍歴すればよい
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];
}
};
accepted