ex2.cpp

来自「上海交通大学本科算法大作业」· C++ 代码 · 共 142 行

#include<iostream>
#include<fstream>
using namespace std;

class Vertices{
public:
		int *w;
		int edgeNum,DFS_Number,father,high,Component;
		void set(int n)
		{
			w=new int[n+1];
			edgeNum=0;
			father=-1;
		}	
		void addEdge(int t)
		{
			edgeNum++;
			w[edgeNum]=t;
		}
};

class Stack{
public:
		void set(int num)
		{	
			s=new int[num];
			n=0;
		}
		int n;//栈内指针
		int *s;
		void insert(int v)
		{
			n++;
			s[n]=v;
		}
		void remove()
		{
			n--;
		}
		int element()
		{
			return s[n];
		}
};	

class Biconnected_Components{
public:
		Vertices *vert;
		Stack stack;
		int subgraph[101][102];
		int DFS_N;
		int num;
		Biconnected_Components()
		{
			int i;
			ifstream inClientFile("data1.txt", ios::in);
			ofstream outClientFile("result1.txt", ios::out);
			int verticeNum;
			if(!inClientFile)
			{
				cout<<"File couldn't be opened!"<<endl;
			}
			inClientFile>>verticeNum;
			vert=new Vertices[verticeNum];
			stack.set(verticeNum);
			for ( i=0; i<verticeNum; i++)
			{
				vert[i].DFS_Number=0;
				vert[i].set(verticeNum);
			}
			while(!inClientFile.eof())
			{
				char t;
				int v,w;
				inClientFile>>t>>v>>t>>w>>t;
				vert[v].addEdge(w);
				vert[w].addEdge(v);
			}
			DFS_N=verticeNum;
			num=0;
			BC(0);	
			outClientFile<<num<<endl;
			for( i=1; i<=num; i++)
			{
				outClientFile<<"(";
				for(int j=1; j<=subgraph[i][0]; j++)
					if(j!=subgraph[i][0])outClientFile<<subgraph[i][j]<<",";
					else outClientFile<<subgraph[i][j]<<")"<<endl;
			}
		}
		
		void BC(int v);

};

void Biconnected_Components::BC(int v)
{
	vert[v].DFS_Number=DFS_N;
	DFS_N--;
	stack.insert(v);
	vert[v].high=vert[v].DFS_Number;
	for(int i=1; i<=vert[v].edgeNum; i++)		
	{
		//不将边加入栈中
		if (vert[v].w[i]!=vert[v].father) 
			if (vert[vert[v].w[i]].DFS_Number==0)
			{
				if(vert[vert[v].w[i]].father==-1) 
					vert[vert[v].w[i]].father=v;
				BC(vert[v].w[i]);
				if (vert[vert[v].w[i]].high<=vert[v].DFS_Number)
				{
					//Stack中到v为止的所有点（包括v）的集合为双连通
					num++;
					int i=0;
					while(stack.element()!=v)
					{
						i++;
						subgraph[num][i]=stack.element();
						stack.remove();
					}
					i++;
					subgraph[num][i]=stack.element();
					subgraph[num][0]=i;
				}
				if(vert[v].high<vert[vert[v].w[i]].high)
					vert[v].high=vert[vert[v].w[i]].high;
			}
			else
				if(vert[v].high<vert[vert[v].w[i]].DFS_Number)
					vert[v].high=vert[vert[v].w[i]].DFS_Number;
	}
}



int main()
{
	Biconnected_Components BC1;
	return 0;
}