着色问题6422color.cpp

设计一个算法

#include<iostream>
#include<fstream>
using namespace std;
ifstream in("input.txt");
ofstream out("output.txt");
class OutOfBounds{};
class Node
{
	friend class Graph;
	friend class Queue;
private:
	int num;
	Node*next;
};
class Queue
{
	friend class Graph;
private:
	Node*front,*rear;
public:
	Queue(){front=rear=0;}
	int Empty(){return ((front)?0:1);}
	Queue Enqueue(int &v);
	Queue Dequeue(int &w);
};
Queue Queue::Enqueue(int &v)
{
	Node*p=new Node;
	p->num=v;
	p->next=0;
	if(front)
		rear->next=p;
	else
		front=p;
	
	rear=p;
	return*this;
}
Queue Queue::Dequeue(int &w)
{
    if(Empty())
		throw OutOfBounds();
	w=front->num;
	Node*p=front;
	front=front->next;
	delete p;
	return*this;
}
class Graph
{
private:
	Node*a;
	int *reach;
	int n;
public:
	Graph(){a=0;n=0;}
    Graph Create();
	int BFS(int v);
	void BFS_plus();
	void Insert(int i,int j);
};
Graph Graph::Create()
{
	in>>n;
	a=new Node[n];
	for(int i=0;i<n;i++)
	{
		a[i].num=i+1;
		a[i].next=0;
	}
	int edge;
	in>>edge;
	for(i=0;i<edge;i++)
	{
		int j,k;
		in>>j>>k;
		Insert(j,k);
		Insert(k,j);
	}
	reach=new int[n];
	for(i=0;i<n;i++)
		reach[i]=-1;
	return*this;
}
void Graph::Insert(int i,int j)
{
	Node*p1=new Node;
	p1->num=i;
	Node*p2=a[j-1].next;
	a[j-1].next=p1;
	p1->next=p2;
}
int Graph::BFS(int v)
{
	int k=0;
	Queue Q;
	reach[v-1]=1;
	Q.Enqueue(v);
	while(!Q.Empty()&&k==0)
	{
		k=0;
		int w;
		Q.Dequeue(w);
		Node*p;
		for(p=a[w-1].next;p&&k==0;p=p->next)
		{
			int u=p->num;
			if(reach[u-1]==reach[w-1])
				k=1;
			else
				if(reach[u-1]==-1)
				{
					reach[u-1]=(!reach[w-1]);
				    Q.Enqueue(u);
				}
		}
	}
	if(k==1)
		return 0;
	else
		return 1;
}
void Graph::BFS_plus()
{
	for(int i=0;i<n;i++)
		if(reach[i]==-1)
		{
			int n=BFS(i+1);
			if(!n)
				break;
		}
	if(i<n)
		out<<"No";
	else
	{
		out<<"Yes"<<endl;
		for(int i=0;i<n;i++)
			out<<reach[i]<<" ";
	}
}
void main()
{
	Graph m;
	m.Create();
	m.BFS_plus();
}