#include <iostream>#include <stdio.h>#include <vector>#include <string>#include <queue>#include <unordered_map>#include <sstream>using namespace std;/*問題:Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.OJ's undirected graph serialization: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 node 0 to both nodes 1 and 2.Second node is labeled as 1. Connect node 1 to node 2.Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.Visually, the graph looks like the following:       1      / /     /   /    0 --- 2         / /         /_/分析:題目是想拷貝一個無向圖。具體要求是對每個結點需要求出其所有鄰接點，并把所有鄰接點存儲到該結點自身的成員變量中。可能存在某些結點指向自身，這種情況，當前結點自身是否存儲?需要的。參見序列化結果對于結點0：鄰接點為1,2，即其成員變量只需要存儲這兩個結點對于結點結點1：給定了鄰接點2，由于0又和2連接，因此雖然結點1存儲的鄰接點為2，但是卻可以連接到0對于結點2：自循環，所以插入結點2現在給定一個有向圖，肯定是比如給定初始結點0，找到鄰接點為1,2，輸出:0,1,2遍歷不等于自身的鄰居結點(防止陷入死循環)1：得到1的鄰接點為2(也可能包含了0，只不過已經訪問過，過濾),輸出:1,2遍歷鄰接點2：輸出:2，2現在猜這個圖原始存的時候比如對于結點1，是否存儲了0？應該是沒有存儲，題目的意思估計就是讓我們存儲一下。否則題目變成了結點的直接new和copy，這個就一個意思，考的是圖的遍歷。既然是拷貝，應該是一樣的。其實考的知識點就是圖的遍歷，如果用廣度優先，隊列來做，設定一個訪問標記，如果當前從隊列中彈出的結點沒有訪問過，就遍歷其所有的鄰居結點，new出和其一樣的；鄰居結點和當前結點對每個未訪問的鄰居結點，壓入到隊列，最后直到隊列為空，結束。這里的關鍵問題在于比如遍歷結點0：結點0沒有訪問過，新建新的結點0，設置已經訪問標記，可能需要設定兩個隊列，一個隊列是原有隊列，存儲廣度優先結果；另一個隊列是存放已經建立的結點題目說：每個結點的標記是唯一的，直接用一個標記<int,Node*>來做輸入：0 1 2#1 2#2 2輸出:0 1 2#1 2#2 2關鍵：1采用廣度優先搜索，建立label指向已經建立好結點的映射。隊列中彈出的結點沒有被訪問過，設置訪問標記    如果該結點的還沒有在拷貝圖中建立，就建立	獲取結點的鄰居結點，遍歷每個鄰居結點，如果拷貝圖中對應鄰居結點沒有建立，也建立	如果鄰居結點已經訪問過，就過濾；否則，壓入隊列*/struct UndirectedGraphNode {   int label;   vector<UndirectedGraphNode *> neighbors;   UndirectedGraphNode(int x) : label(x) {};};class Solution {public:	UndirectedGraphNode* bfs(UndirectedGraphNode *node,unordered_map<int , UndirectedGraphNode*>& hasBuilt)	{		if(!node)		{			return NULL;		}		queue<UndirectedGraphNode *> nodes;		nodes.push(node);		UndirectedGraphNode* curNode;		unordered_map<UndirectedGraphNode* , bool> visited;		vector<UndirectedGraphNode *> neighbours;		UndirectedGraphNode* root = NULL;		UndirectedGraphNode* nextNode = NULL;		bool isFirst = true;		UndirectedGraphNode* newNode = NULL;		while(!nodes.empty())		{			curNode = nodes.front();			nodes.pop();			if(!curNode)			{				continue;			}			//如果當前結點已經訪問過，直接跳過			if(visited.find(curNode) != visited.end())			{				continue;			}			visited[curNode] = true;//設置當前結點已經訪問			//如果當前訪問的結點沒有建立			if(hasBuilt.find(curNode->label) == hasBuilt.end())			{				//這里有一個問題，結點1已經作為鄰居結點被訪問過了了，被建立過了，這里又要新建一遍				newNode = new UndirectedGraphNode(curNode->label);				hasBuilt[curNode->label] = newNode;			}			else			{				newNode = hasBuilt[curNode->label] ;			}			//保存首結點，用于返回			if(isFirst)			{				root = newNode;				isFirst = false;			}			vector<UndirectedGraphNode* > myNeighbours;			neighbours = curNode->neighbors;			if(neighbours.empty())			{				newNode->neighbors = myNeighbours;				continue;			}			int size = neighbours.size();			for(int i = 0 ; i < size ; i++)			{				nextNode = neighbours.at(i);				//如果鄰居結點為空，直接跳過				if(!nextNode)				{					myNeighbours.push_back(NULL);					continue;				}				//判斷鄰居結點是否已經建立，如果沒有建立，才建立。這里有個問題，結點2其實已經建立過了				if(hasBuilt.find(nextNode->label) == hasBuilt.end())				{					UndirectedGraphNode* tempNode = new UndirectedGraphNode(nextNode->label);					myNeighbours.push_back(tempNode);					hasBuilt[nextNode->label] = tempNode;				}				else				{					myNeighbours.push_back(hasBuilt[nextNode->label]);				}				//如果鄰居結點已經訪問過，就不壓入隊列				if(visited.find(nextNode) != visited.end())				{					continue;				}				nodes.push(nextNode);			}			//所有結點建立好之后，下面設定鄰居結點集合			newNode->neighbors = myNeighbours;		}		return root;	}    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {		unordered_map<int , UndirectedGraphNode*> hasBuilt;        UndirectedGraphNode* root = bfs(node, hasBuilt);		_hasBuilt = hasBuilt;		_root = root;		return root;    }public:	UndirectedGraphNode* _root;	unordered_map<int , UndirectedGraphNode*> _hasBuilt;};vector<string> split(string& str , string& splitStr){	vector<string> result;	if(str.empty())	{		return result;	}	if(splitStr.empty())	{		result.push_back(str);		return result;	}	int beg = 0;	size_t pos = str.find(splitStr);	string partialStr;	while(string::npos != pos)	{		partialStr = str.substr(beg , pos - beg);		if(!partialStr.empty())		{			result.push_back(partialStr);		}		beg = pos + splitStr.length();		pos = str.find(splitStr , beg);	}	//防止 aa#aa，這種最后一次找不到	partialStr = str.substr(beg , pos - beg);	if(!partialStr.empty())	{		result.push_back(partialStr);	}	return result;}//按"# "號分割，然后按空格分割，0 1 2#1 2#2 2UndirectedGraphNode* buildGraph(string& str , unordered_map<int,UndirectedGraphNode* >& hasBuilt){	vector<string> result = split(str , string("#"));	if(result.empty())	{		return NULL;	}	vector<vector<string> > lines;	int size = result.size();	for(int i = 0 ; i < size ; i++)	{		vector<string> Words = split(result.at(i) , string(" "));		lines.push_back(words);	}	if(lines.empty())	{		return NULL;	}	//接下來找到所有的結點: 0 1 2 , 1 2 , 2 2	int lineSize = lines.size();	int wordSize;	UndirectedGraphNode* node = NULL ;	for(int i = 0 ; i < lineSize ; i++ )	{		wordSize=  lines.at(i).size();		UndirectedGraphNode* begNode = NULL;		vector<UndirectedGraphNode*> neighbours;		for(int j = 0 ; j < wordSize ; j++)		{			int value = atoi(lines.at(i).at(j).c_str());			//如果沒有建立			if(hasBuilt.find(value) == hasBuilt.end())			{				node = new UndirectedGraphNode(value);				hasBuilt[value] = node;			}			else			{				node = hasBuilt[value];			}			//確定結點指向			if(j)			{				neighbours.push_back(node);			}			//根節點，需要建立指向			else			{				begNode = node;			}		}		begNode->neighbors = neighbours;	}	int value = atoi( lines.at(0).at(0).c_str());	return hasBuilt[value];}//如何遞歸刪除圖的所有結點，廣度優先搜索(有環)，無需這樣刪除，之前不是保存了建立//結點的map嗎。刪除這個void deleteGraph(unordered_map<int , UndirectedGraphNode* > hasBuilt){	for(unordered_map<int , UndirectedGraphNode*>::iterator it = hasBuilt.begin() ; 		it != hasBuilt.end() ; it++)	{		delete it->second;		it->second = NULL;	}}//如何構建這個有向圖string myBFS(UndirectedGraphNode* node){	queue<UndirectedGraphNode*> nodes;	nodes.push(node);	unordered_map<UndirectedGraphNode* , bool> visited;	vector<vector<int> >results;	vector<int> result;	while(!nodes.empty())	{		UndirectedGraphNode* curNode = nodes.front();		nodes.pop();		//如果當前結點已經訪問過		if(visited.find(curNode) != visited.end())		{			continue;		}		visited[curNode] = true;		result.push_back(curNode->label);		//當前結點已經訪問過，因此，需要		vector<UndirectedGraphNode*> neightbours = curNode->neighbors;		if(neightbours.empty())		{			continue;		}		int size = neightbours.size();		for(int i = 0 ; i < size ; i++)		{			UndirectedGraphNode* nextNode = neightbours.at(i);			if(!nextNode)			{				continue;			}			result.push_back(nextNode->label);			//子節點必須未被訪問過			if(visited.find(nextNode) != visited.end())			{				continue;			}			nodes.push(nextNode);		}		results.push_back(result);		result.clear();	}	//轉換結果	if(results.empty())	{		return "";	}	int size = results.size();	int len;	stringstream resultStream;	for(int i = 0 ; i < size ; i++)	{		stringstream stream;		len = results.at(i).size();		for(int j = 0 ; j < len ; j++)		{			stream << results.at(i).at(j) << " ";		}		stream << "#";		resultStream << stream.str();	}	return resultStream.str();}void PRint(vector<int>& result){	if(result.empty())	{		cout << "no result" << endl;		return;	}	int size = result.size();	for(int i = 0 ; i < size ; i++)	{		cout << result.at(i) << " " ;	}	cout << endl;}void process(){	 vector<int> nums;	 Solution solution;	 vector<int> result;	 char str[1024];	 while(gets(str))	 {		 string value(str);		 unordered_map<int , UndirectedGraphNode*> hasBuilt;		 UndirectedGraphNode* root = buildGraph(value, hasBuilt);		 UndirectedGraphNode* newRoot = solution.cloneGraph(root);		 string origin = myBFS(root);		 cout << origin << endl;		 string newResult = myBFS(newRoot);		 cout << newResult << endl;		 deleteGraph(hasBuilt);		 deleteGraph(solution._hasBuilt);	 }}int main(int argc , char* argv[]){	process();	getchar();	return 0;}