首页 > 代码库 > leetcode Clone Graph
leetcode Clone Graph
复制一个无向图。图的结构时有一个label,一个vector存和他想接的节点。可以自循环,就是vector中可以存在自己。例如:
Nodes are labeled uniquely.
We use#
as a separator for each node, and ,
as a separator for node label and each neighbor of the node.As an example, consider the serialized graph {0,1,2#1,2#2,2}
.
The graph has a total of three nodes, and therefore contains three parts as separated by #
.
- First node is labeled as
0
. Connect node0
to both nodes1
and2
. - Second node is labeled as
1
. Connect node1
to node2
. - Third node is labeled as
2
. Connect node2
to node2
(itself), thus forming a self-cycle.
Visually, the graph looks like the following:
1 / / 0 --- 2 / \_/
思路:一开始,我就想到用BFS,但是需要判断是否已经处理过该节点,因为存在循环。避免死循环就要用一个可以O1时间访问否值是否存在的东东来存已经访问过的节点,那就是map了,或者是set,我用set存访问过的,然后两个queue来同步的走,及把node复制到另一个root中,然后que和que2分别表示需要继续BFS处理的后序节点。非迭代的:
/** * Definition for undirected graph. * struct UndirectedGraphNode { * int label; * vector<UndirectedGraphNode *> neighbors; * UndirectedGraphNode(int x) : label(x) {}; * }; */class Solution { public: UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) { if (!node) return node; //if ((node -> neighbors).size() == 0) return node; queue<UndirectedGraphNode *> que, que2; que.push(node); UndirectedGraphNode *root = new UndirectedGraphNode(node -> label), *tmp, *subnode, *tmp2; unordered_set<UndirectedGraphNode*> uset; que2.push(root); while(!que.empty()) { tmp = que.front(); tmp2 = que2.front(); uset.insert(tmp); que.pop(); que2.pop(); for (int i = 0; i < tmp -> neighbors.size(); ++i) { if (tmp -> neighbors[i] == tmp) subnode = tmp2; else subnode = new UndirectedGraphNode(tmp -> neighbors[i] -> label); tmp2 -> neighbors.push_back(subnode); if (uset.count(tmp -> neighbors[i]) == 0) { que.push(tmp -> neighbors[i]); que2.push(subnode); } } } return root; }};
但是超时了,可能最近感冒脑子不灵活了哎。
不知道为什么上面用两个队列会超时啊。换成map的映射的话就不会超时:
unordered_map(UndirectedGraphNode *, UndirectedGraphNode *) copied; 指key对应的node是否在value对应的node中复制。
因为是BFS要用一个que来存自己已经复制,但是他的neighbors还没有复制的节点。那么初始化que就要push一个node,而copied[node]就是赋值为node->label对应的新节点。
然后根据que是否为空处理。
/** * Definition for undirected graph. * struct UndirectedGraphNode { * int label; * vector<UndirectedGraphNode *> neighbors; * UndirectedGraphNode(int x) : label(x) {}; * }; */class Solution { public: UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) { if (!node) return node; unordered_map<UndirectedGraphNode *, UndirectedGraphNode *> copied; queue<UndirectedGraphNode *> que; que.push(node); copied[node] = new UndirectedGraphNode(node -> label); while(!que.empty()) { UndirectedGraphNode *cur = que.front(); que.pop(); for (int i = 0; i < cur -> neighbors.size(); ++i) { if (copied.count(cur->neighbors[i])) copied[cur] -> neighbors.push_back(copied[cur -> neighbors[i]]); else { UndirectedGraphNode *new_node = new UndirectedGraphNode(cur -> neighbors[i] -> label); copied[cur -> neighbors[i]] = new_node; copied[cur] -> neighbors.push_back(new_node); que.push(cur -> neighbors[i]); } } } return copied[node]; }};
这有DFS
leetcode Clone Graph
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。