/************************************************************************/
/*                       Cayley 定理                                    */
/************************************************************************/
#include <iostream>
#include <map>
#include <algorithm>
#include <list>
#include <utility>
#include <vector>
using namespace std;

typedef map<int ,list<int>* >::value_type value_type; 

class Cayley
{
public:
	Cayley():x(x),y(y),k(10000),num_map(0),num_list(0),map_size(map_size){}
	~Cayley(){delete num_list;delete num_map;}
	void Creattree();
	void Deletenode();
private:	
	map<int,list<int>*> *num_map;
	list<int> * num_list;
	int x,y,k,map_size;
};
void main()
{
	Cayley q;
	q.Creattree();
	q.Deletenode();
}

void Cayley::Creattree()
{
	num_map = new map<int,list<int>* >;                       
	while (1)
	{
		cout<<"Enter node ,-1 over:"<<endl;
		cin>>x;
		if (x==-1)
		{
			break;
		}
		num_list =new list<int>;
		num_map->insert(value_type(x,num_list));
	}
			
		map<int,list<int>* >::iterator it = num_map->begin(),end_it = num_map->end();

			while (it!=end_it)
			{
				while (1)
				{
					cout<<"Enter("<<it->first<<"):Child,0 over"<<endl;	
			        cin>>y;	
			        if (y==0)
					{
				        break;
					}	
				    it->second->push_back(y);
				}
				it++;	
			}	
}
	
void Cayley::Deletenode()
{
	map_size = num_map->size();
	vector <int> * svec = new vector<int>;              //b
	ostream_iterator<int> screen(cout," ");

  while(map_size>2)
  {
	map<int,list<int>* >::iterator it = num_map->begin(),end_it = num_map->end();
	while (it!=end_it)
	{
		for (int i=1;i<=map_size;i++)
		{
			if (it->second->empty())
			{
				if (it->first<k)
				{
				    k=it->first;				
				}
			}			
		}
		it++;
	}
	cout<<"a="<<k<<endl;
	
	num_map->erase(k);
	map_size--;

	it = num_map->begin(),end_it = num_map->end();
	
	while (it!=end_it)
	{
		list<int> * edge_list = it->second;
		list<int>::iterator list_it = edge_list->begin(),list_end_it = edge_list->end();
		
		for (;list_it!=list_end_it;list_it++)
		{
			if (*list_it==k)
			{
				svec->push_back(it->first);
				edge_list->remove(*list_it);
				break;
			}
		}	
		it++;
	}
       k=10000;
  }

  cout<<"b序列為:"<<endl;
  copy(svec->begin(),svec->end(),screen);
  cout<<endl;
}