cpp1.cpp

求强连通分支

//welldone by Sunny in SJTU
#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()
		{
			ifstream inClientFile("data3.dat", ios::in);
			ofstream outClientFile("result3.txt", ios::out);
			int verticeNum;
			if(!inClientFile)
			{
				cout<<"File couldn't be opened!"<<endl;
			}
			inClientFile>>verticeNum;
			vert=new Vertices[verticeNum];
			stack.set(verticeNum);
			for (int 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;
	}
}

class Strongly_Connected{
public:
		Vertices *vert;
		Stack stack;
		int subgraph[101][102];
		int DFS_N;
		int num;
		int verticeNum,Current_Component;
		Strongly_Connected()
		{
			ifstream inClientFile("data4.dat", ios::in);
			ofstream outClientFile("result4.txt", ios::out);
			
			if(!inClientFile)
			{
				cout<<"File couldn't be opened!"<<endl;
			}
			inClientFile>>verticeNum;
			vert=new Vertices[verticeNum];
			stack.set(verticeNum);
			for (int i=0; i<verticeNum; i++)
			{
				vert[i].DFS_Number=0;
				vert[i].Component=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;
			Current_Component=0;
			num=0;
			int v;
			while (v=unvisited()>=0)
				SCC(v);	
			outClientFile<<Current_Component<<endl;
			for(i=1; i<=Current_Component; 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 SCC(int v);
		int unvisited();
};

int Strongly_Connected::unvisited()
{
	for(int i=0; i<verticeNum; i++)
		if(vert[i].DFS_Number==0)
			return i;
	return -1;
}

void Strongly_Connected::SCC(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[vert[v].w[i]].DFS_Number==0)
		{
			SCC(vert[v].w[i]);
			if(vert[v].high<vert[vert[v].w[i]].high)
				vert[v].high=vert[vert[v].w[i]].high;
		}
		else
		{
			if((vert[vert[v].w[i]].DFS_Number>vert[v].DFS_Number)&&(vert[vert[v].w[i]].Component==0))
				if(vert[v].high<vert[vert[v].w[i]].DFS_Number)
					vert[v].high=vert[vert[v].w[i]].DFS_Number;
		}
	}
	if(vert[v].high==vert[v].DFS_Number)
	{
		Current_Component++;
		int i=0;
		while(stack.element()!=v)
		{
			i++;
			subgraph[Current_Component][i]=stack.element();
			vert[stack.element()].Component=Current_Component;
			stack.remove();
		}
		i++;
		subgraph[Current_Component][i]=stack.element();
		vert[stack.element()].Component=Current_Component;
		stack.remove();
		subgraph[Current_Component][0]=i;
	}	
}

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