好双回路问题546euler2.cpp

设计一个算法

#include<iostream>
#include<fstream>

using namespace std;



ofstream out("output.txt");

class EdgeNode
{
public:
    EdgeNode(int pre,int pos);
	int pre_v,
		pos_v;                                                            //与边关联的两个顶点
};///:p

EdgeNode::EdgeNode(int pre,int pos)
{
	pre_v=pre;
	pos_v=pos;
}///:p


void Make2DArray(int **&x,int rows,int cols,int noEdge)
{
	x=new int *[rows];
	if(x==NULL)
	{
		exit(1);
	}
	for(int i=0;i<rows;i++)
	{
		x[i]=new int [cols];
		if(x[i]==NULL)
		{
			exit(1);
		}

		memset(x[i],noEdge,sizeof(int)*rows);
	}
}///:p

void Delete2DArray(int **&x,int rows)
{
	for(int i=0; i<rows; i++)
	{
		delete [] x[i];
	}
	delete [] x;
	x=NULL;
}///:p



class AdjacencyWDigraph
{

	friend class AdjacencyGraph;

public:
	AdjacencyWDigraph(int Vertices=10, int noEdge=0);
	~AdjacencyWDigraph();
	bool Exist(int i,int j) const;
	int Edges()const{return e;}
	int Vertices()const{return n;}
	AdjacencyWDigraph&Add(int i,int j,const int &w);
	AdjacencyWDigraph&Delete(int i,int j);
	int OutDegree(int i) const;
	int InDegree(int i) const;
	void Output() const;
	int Begin(int i);
	int NextVertex(int i);
	void dfs(EdgeNode &E,int reach[],int label);
	void DFS(int v,int label,int reach[]);
	void print_v(EdgeNode &E);
	void InitializePos()
	{
		pos=new int [n+1];
		if(pos==NULL)
		{
			exit(1);
		}
	}
    void DeactivatePos()
	{
		delete [] pos;
	}

private:
	int NoEdge;
	int n;
	int e;
	int **a;
	int *pos;
};///:p

AdjacencyWDigraph::AdjacencyWDigraph(int Vertices,int noEdge)
{
	n=Vertices;
	e=0;
	NoEdge=noEdge;
	Make2DArray(a,n+1,n+1,noEdge);

}///:p

AdjacencyWDigraph::~AdjacencyWDigraph()
{
	Delete2DArray(a,n+1);
}///:p


bool AdjacencyWDigraph::Exist(int i,int j) const
{
	if(i<1||j<1||i>n||j>n||a[i][j]==NoEdge)
	{
		return false;
	}
	return true;
}///:p

AdjacencyWDigraph &AdjacencyWDigraph::Add(int i,int j,const int &w)
{
	if(i<1||j<1||i>n||i==j||a[i][j]!=NoEdge)
	{
		exit(1);
	}
	a[i][j]=w;
	e++;
	return *this;
}///:p

AdjacencyWDigraph &AdjacencyWDigraph::Delete(int i,int j)
{
	if(i<1||j<1||i>n||j>n||a[i][j]==NoEdge)
	{
		exit(1);
	}
	a[i][j]=NoEdge;
	e--;
	return *this;
}///:p

int AdjacencyWDigraph::OutDegree(int i) const
{
	if(i<1||i>n)
	{
		exit(1);
	}
	int sum=0;
	for(int j=1;j<=n;j++)
	{
		if(a[i][j]!=NoEdge)
		{
			sum++;
		}
	}
	return sum;
}///:p

int AdjacencyWDigraph::InDegree(int i) const
{
	if(i<1||i>n)
	{
		exit(1);
	}
	int sum=0;
	for(int j=1;j<=n;j++)
	{
		if(a[j][i]!=NoEdge)
		{
			sum++;
		}
	}
	return sum;
}///:p

void AdjacencyWDigraph::Output() const
{
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			cout<<a[i][j]<<' ';
		}
		cout<<endl;
	}
}///:p

int AdjacencyWDigraph::Begin(int i)
{
	if(i<1||i>n)
	{
		exit(1);
	}
	for(int j=1;j<=n;j++)
	{
		if(a[i][j]!=NoEdge)
		{
			pos[i]=j;
			return j;
		}
	}
	pos[i]=n+1;
	return 0;
}///:p

int AdjacencyWDigraph::NextVertex(int i)
{
	if(i<1||i>n)
	{
		exit(1);
	}
	for(int j=pos[i]+1;j<=n;j++)
	{
		if(a[i][j]!=NoEdge)
		{
			pos[i]=j;
			return j;
		}
	}
	pos[i]=n+1;
	return 0;
}///:p

void AdjacencyWDigraph::print_v(EdgeNode &E)
{
	a[E.pre_v][E.pos_v]=NoEdge;
	a[E.pos_v][E.pre_v]=NoEdge;
	if(E.pos_v!=0)
	{
        out<<E.pos_v<<' ';
	}

}///:p

void AdjacencyWDigraph::DFS(int v,int lable,int reach[])
{
	this->InitializePos();
	EdgeNode edge(0,v);
	dfs(edge,reach,lable);
	this->DeactivatePos();
}///:p

void AdjacencyWDigraph::dfs(EdgeNode &edge,int reach[],int lable)
{
	print_v(edge);
	reach[edge.pos_v]=lable;

	EdgeNode temp_edge(edge.pos_v,Begin(edge.pos_v));

	while(temp_edge.pos_v!=0)
	{
        if(reach[temp_edge.pos_v]==0)
		{
			dfs(temp_edge,reach,lable);
		}

	    if(reach[temp_edge.pos_v]==lable && a[temp_edge.pre_v][temp_edge.pos_v]!=NoEdge && a[temp_edge.pos_v][temp_edge.pre_v]!=NoEdge)
		{
			print_v(temp_edge);	
			EdgeNode temp2_edge(temp_edge.pos_v,temp_edge.pre_v);
			print_v(temp2_edge);
		}

		temp_edge.pos_v=NextVertex(edge.pos_v);
	}

	EdgeNode temp2_edge(edge.pos_v,edge.pre_v);
	print_v(temp2_edge);
}///:p



class AdjacencyGraph: public AdjacencyWDigraph
{

public:
	AdjacencyGraph(int Vertices=10):AdjacencyWDigraph(Vertices,0){}
	AdjacencyWDigraph &Add(int i,int j);
	AdjacencyGraph &Delete(int i,int j);
	int Degree(int i) const;
};///:p

AdjacencyWDigraph &AdjacencyGraph::Add(int i,int j)
{
	AdjacencyWDigraph::Add (i,j,1);
    AdjacencyWDigraph::Add (j,i,1);
	return *this;
}///:p

AdjacencyGraph &AdjacencyGraph::Delete(int i,int j)
{
	AdjacencyWDigraph::Delete(i,j);
	AdjacencyWDigraph::Delete(j,i);
	return *this;
}///:p

int AdjacencyGraph::Degree(int i) const
{
	return OutDegree(i);
}///:p



int main()
{
	ifstream in("input.txt");
	if(in.fail())
	{
		exit(1);
	}

	int Vertices_num,
		Edges_num;
	in>>Vertices_num
	  >>Edges_num;

    AdjacencyGraph OP_Graph(Vertices_num);

	for(int i=0; i<Edges_num; i++)
	{
        int v_1, v_2;
		in>>v_1>>v_2;
		OP_Graph.Add(v_1,v_2);
	}
	
	int *reach=new int [Vertices_num+1];
	if(reach==NULL)
	{
		exit(1);
	}
	memset(reach,0,sizeof(int)*(Vertices_num+1));

	OP_Graph.DFS(1,1,reach);

	delete [] reach;
	reach=NULL;

	return 0;
}