net.cpp

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

#include<iostream.h>
#include<fstream.h>
#include<stdlib.h>
template<class T>
class Iterator;
template<class T>
class List;
template<class T>
class Stack;
template<class T>
class Node
{
	friend List<T>;
	friend Stack<T>;
    friend Iterator<T>;
	private:
		T data;
		Node<T>*next;
};
template<class T>
class List{
	private:
		Node<T>*first;
	public:
		friend Iterator<T>;
		List(){first=0;}
		List<T>&Insert (int k,const T&x)
		   {
			Node<T>*p=first;
		   for(int index=1;index<k&&p;index++)
			p=p->next;
		   Node<T>*y=new Node<T>;
		   y->data=x;
		   if(k)
		   {
			   y->next=p->next;
		   p->next=y;
		   }
		   else{
			   y->next=first;
			   first=y;
		   }
		   return *this;
		   }
};
template<class T>
class Stack
{
	private:
		Node<T>*top;
	public:
		Stack(){top=0;}
		   bool Empty()const{return top==0;}
		   Stack<T>&Push(const T&x)
		   {
		   Node<T>*p=new Node<T>;
		   p->data=x;
		   p->next=top;
		   top=p;
		   return *this;
		   }
		   Stack<T>&Pop(T&x)
		   {
			   x=top->data;
			   Node<T>*p=top;
			   top=top->next;
			   delete p;
			   return *this;
		   }
};
template<class T>
class Iterator 
	{
	private:
		Node<T>*location;
	public:
		T* Init(const List<T>&c)
		   {
			   location=c.first;
			   if (location)return &location->data;
			   return 0;
		   }
		   T*Next()
		   {
			   if(!location)return 0;
			   location=location->next;
			   if(location)return &location->data;
			   return 0;
		   }
};
int main()
{
	int n,r,m=0;
	ifstream in("input.txt");
	ofstream out("output.txt");
	in>>n;
	if(n<2){exit(1);}
	in>>r;
	if(r<1){exit(1);}
	List<int>*L;
	L=new List<int>[n+1];
	for(int i=1;i<=r;i++)
	{
		int a,b;
		in>>a>>b;
		L[a].Insert(0,b);
		L[b].Insert(0,a);
	}
	Stack<int>stack;
		bool *out1;
		out1=new bool[n+1];
		for( i=1;i<=n;i++)
			out1[i]=false;
		for(i=1;i<=n;i++)
			if(!out1[i])
			{	m++;
				out1[i]=true;
				stack.Push(i);
				while (!stack.Empty())
				{
					int *q,j;
					stack.Pop(j);
					Iterator<int>c;
					q=c.Init(L[j]);
					while(q)
					{
						if(!out1[*q])
						{
							out1[*q]=true;
							stack.Push(*q);
						}
						q=c.Next();
					}
			}
	}
	out<<m<<endl;	
	return 0;		
}