- #刷题
- #leetcode
Clone Graph 问题出错(Output Limit Exceeded)

17342
用dfs写的,debug了半天,找不出问题,找版上大牛求助!
#include <iostream>[br][/br][br][/br]#include <vector>[br][/br][br][/br]using namespace std;[br][/br][br][/br]struct UndirectedGraphNode {[br][/br][br][/br] int label;[br][/br][br][/br] vector<UndirectedGraphNode *> neighbors;[br][/br][br][/br] UndirectedGraphNode(int x) : label(x) {};[br][/br][br][/br]};[br][/br][br][/br]class Solution {[br][/br][br][/br]public:[br][/br][br][/br] UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {[br][/br][br][/br] if (node == NULL) return NULL;[br][/br][br][/br] UndirectedGraphNode *head = new UndirectedGraphNode(node->label);[br][/br][br][/br] dfs(node, head);[br][/br][br][/br] return head;[br][/br][br][/br] }[br][/br][br][/br] void dfs(UndirectedGraphNode *node, UndirectedGraphNode *copy) {[br][/br][br][/br] if ( !is_visited(node) ) {[br][/br][br][/br] visited.push_back(node->label); [br][/br][br][/br] //cout << node->label << endl;[br][/br][br][/br] vector<UndirectedGraphNode *> vec = node->neighbors;[br][/br][br][/br] for (int i=0; i<vec.size(); i++) {[br][/br][br][/br] UndirectedGraphNode *n = new UndirectedGraphNode(vec[i]->label);[br][/br][br][/br] copy->neighbors.push_back(n); [br][/br][br][/br] //cout << n->label << ": " << vec[i]->label << endl; [br][/br][br][/br] dfs(vec[i], n);[br][/br][br][/br] }[br][/br][br][/br] } [br][/br][br][/br] }[br][/br][br][/br] bool is_visited(UndirectedGraphNode *node) {[br][/br][br][/br] for (int i=0; i<visited.size(); i++) {[br][/br][br][/br] if (visited[i] == node->label) return true;[br][/br][br][/br] }[br][/br][br][/br] return false;[br][/br][br][/br] } [br][/br][br][/br]private:[br][/br][br][/br] vector<int> visited;[br][/br][br][/br]};[br][/br][br][/br] vector<int> visited;[br][/br][br][/br] bool is_visited(UndirectedGraphNode *node) {[br][/br][br][/br] for (int i=0; i<visited.size(); i++) {[br][/br][br][/br] if (visited[i] == node->label) return true;[br][/br][br][/br] }[br][/br][br][/br] return false;[br][/br][br][/br] }[br][/br][br][/br] void dfs(UndirectedGraphNode *node) {[br][/br][br][/br] if ( !is_visited(node) ) {[br][/br][br][/br] visited.push_back(node->label); [br][/br][br][/br] //cout << node->label << endl;[br][/br][br][/br] vector<UndirectedGraphNode *> vec = node->neighbors;[br][/br][br][/br] for (int i=0; i<vec.size(); i++) {[br][/br][br][/br] cout << node->label << "->neighbors: " << vec[i]->label << endl; [br][/br][br][/br] dfs(vec[i]);[br][/br][br][/br] }[br][/br][br][/br] } [br][/br][br][/br] }[br][/br][br][/br] [br][/br][br][/br]int main()[br][/br][br][/br]{[br][/br][br][/br] UndirectedGraphNode *node0 = new UndirectedGraphNode(0);[br][/br][br][/br] UndirectedGraphNode *node1 = new UndirectedGraphNode(1);[br][/br][br][/br] UndirectedGraphNode *node2 = new UndirectedGraphNode(2);[br][/br][br][/br] [br][/br][br][/br] node0->neighbors.push_back(node1); [br][/br][br][/br] node0->neighbors.push_back(node2); [br][/br][br][/br] node0->neighbors.push_back(node0); [br][/br][br][/br] node0->neighbors.push_back(node0); [br][/br][br][/br] node1->neighbors.push_back(node0);[br][/br][br][/br] node1->neighbors.push_back(node2);[br][/br][br][/br] node2->neighbors.push_back(node0);[br][/br][br][/br] node2->neighbors.push_back(node1);[br][/br][br][/br] Solution s;[br][/br][br][/br] UndirectedGraphNode *n = s.cloneGraph(node0);[br][/br][br][/br] //cout << n->neighbors[0]->label << endl;[br][/br][br][/br] //cout << n->neighbors[1]->label << endl;[br][/br][br][/br] //cout << n->neighbors.size() << endl;[br][/br][br][/br] dfs(n);[br][/br][br][/br]}[/i][/i][/i][/i][/i][/i][/i]
2条回复
热度排序