登录
  • #刷题
  • #leetcode

Clone Graph 问题出错(Output Limit Exceeded)

fangl086
1734
2
用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条回复
热度排序

发表回复