euler.cpp

FZU 大二 的数据结构与算法 老师出的题目的优秀作业 第2到第5章

#include <iostream.h>
#include <fstream.h>
#include<iomanip.h>
int sign=1;
class List;
class Node
{
	public:
		 int data;
		 Node *next;
};
class List
{     
	friend class List;
    public:
		List()   {first=0;}
		const bool Empty()  {return first==0? 1:0;}
		const int Length();
		List &Insert(const int &x);
		List &Delete(int &x);
		Node *first;
};
const int List::Length()
{
	Node *current=first;
	int l=0;
	while(current)
	{
		l++;
		current=current->next;
	}
	return l;
}
List &List::Insert(const int &x)
{
	Node *h=new Node;
	h->data=x;
	h->next=first;
	first=h;
	return *this;
}
List &List::Delete(int &x)
{
	Node *current=first,*k=0;
	while( current && current->data!=x)
	{
		k=current;
		current=current->next;
	}
	if(!current)
	{
		cout<<'-1'<<endl;
		sign=0;
	}
	x=current->data;
	if(k)
		k->next=current->next;
	else
		first=current->next;
	delete current;
	return *this;
}
int main()
{
	ifstream in("input.txt");
    ofstream out("output.txt");
	int n,m,v,w,IND=0,s;  
    in>>n>>m;
	if(m<n)
	{
		out<<"-1\n";
	}
	int *p=new int[m+1];
	List *list=new List[n+1];
	for(int i=0;i<m;i++)
	{
		in>>v>>w;
		list[v].Insert(w);
		list[w].Insert(v);
	}
	s=list[1].first->data;
	i=1;
	p[IND++]=1;
	while(sign && IND<=m)
	{
	    p[IND++]=s;
		list[i].Delete(s);
		list[s].Delete(i);
		i=s;
		if(!list[i].Empty())
			s=list[i].first->data;
	}
	if(p[m-1]==1 || p[m]!=1)
		out<<'-1'<<endl;
	else
	{
	  for(i=0;i<=m;i++)
		  out<<p[i]<<' ';
	      out<<'\n';
	}
	return 1;
}