Cod sursa(job #1948874)

Utilizator GabiTulbaGabi Tulba-Lecu GabiTulba Data 1 aprilie 2017 14:59:49
Problema Componente biconexe Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 3.9 kb
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#define MaxN 100005
#define vertex first
#define colour second
#define INF 2140000000
using namespace std;
  
FILE*IN,*OUT;

int N,M,X,Y,Father[MaxN],Low[MaxN],Cnt=0,Colour=0,Comp=0,Depth[MaxN],Sort[MaxN],Size=0,Stack[MaxN],Index[MaxN],depth=0,Col[MaxN];
bool found[MaxN];
queue<int>Q;
vector<int> Graph[MaxN],Back[MaxN],Out[MaxN];
vector<pair<int,int> >T[MaxN];
void Topological_Sort(int vertex)
{
	bool stop=false;
	depth=0;
	Stack[++depth]=vertex;
	Index[depth]=0;
	while(depth)
	{
		vertex=Stack[depth];
		if(Index[depth]==0)
			found[vertex]=true;
		stop=false;
		for(int i=Index[depth];i<T[vertex].size();i++)
		{
			Index[depth]++;
			if(!found[T[vertex][i].vertex])
			{
				Stack[++depth]=T[vertex][i].vertex;
				stop=true;
				Index[depth]=0;
				break;
			}
		}
		if(!stop)
			Sort[++Size]=Stack[depth],depth--;
	}
}
void Get_Back(int vertex,int father)
{
	Stack[++depth]=vertex;
	Index[depth]=0;
	bool stop=false;
	while(depth)
	{		
		vertex=Stack[depth];
		father=Stack[depth-1];
		if(Index[depth]==0)
		{
			Depth[vertex]=depth;
			found[vertex]=true;
			Father[vertex]=father;
			Low[vertex]=vertex;
		}
		stop=false;
		for(int i=Index[depth];i<Graph[vertex].size();i++)
		{
			Index[depth]++;
			if(!found[Graph[vertex][i]])
			{
				T[vertex].push_back(make_pair(Graph[vertex][i],-1));
				Stack[++depth]=Graph[vertex][i];
				stop=true;
				Index[depth]=0;
				break;
			}
			else if(Depth[vertex]+1<Depth[Graph[vertex][i]])
				Back[vertex].push_back(Graph[vertex][i]);
		}
		if(!stop)
			depth--;
	}
}
void Get_Low(int vertex)
{
	int L=Low[vertex];
	for(int i=0;i<Back[vertex].size();i++)
		if(Low[Back[vertex][i]]!=L)Q.push(Back[vertex][i]);
	while(!Q.empty())
	{
		if(Low[Q.front()]!=L)
			Low[Q.front()]=L,Q.push(Father[Q.front()]);
		Q.pop();
		
	}
}
void Mark_Edges(int vertex,int C)
{
	bool stop=false;
	depth=0;
	Stack[++depth]=vertex;
	Index[depth]=0;
	while(depth)
	{
		vertex=Stack[depth];
		C=Col[depth];
		stop=false;
		for(int i=Index[depth];i<T[vertex].size();i++)
		{
			Index[depth]++;
			if(Low[T[vertex][i].vertex]==Low[Father[vertex]])
			{
				T[vertex][i].colour=C;
				Stack[++depth]=T[vertex][i].vertex;
				Index[depth]=0;
				Col[depth]=C;
				stop=true;
				break;
			}
			else
			{
				T[vertex][i].colour=++Colour;
				Stack[++depth]=T[vertex][i].vertex;
				Index[depth]=0;
				Col[depth]=Colour;
				stop=true;
				break;
			}
		}
		if(!stop)
			depth--;
	}
}
void Get_Comp(int vertex,int C)
{
	bool stop=false;
	depth=0;
	Stack[++depth]=vertex;
	Index[depth]=0;
	while(depth)
	{
		vertex=Stack[depth];
		if(Index[depth]==0)
			Out[Comp].push_back(vertex);
		stop=false;
		for(int i=Index[depth];i<T[vertex].size();i++)
		{
			Index[depth]++;
			if(T[vertex][i].colour==C)
			{
				Stack[++depth]=T[vertex][i].vertex;
				Index[depth]=0;
				stop=true;
				break;
			}
		}
		if(!stop)
			depth--;
	}
}
void Get_BCC(int vertex)
{
	for(int i=0;i<T[vertex].size();i++)
		if(!found[T[vertex][i].colour])
		{
			found[T[vertex][i].colour]=true;
			Out[++Comp].push_back(vertex);
			Get_Comp(T[vertex][i].vertex,T[vertex][i].colour);
		}
}
int main()
{
    IN=fopen("biconex.in","r");
    OUT=fopen("biconex.out","w");
	
	fscanf(IN,"%d%d",&N,&M);

	for(int i=1;i<=M;i++)
	{
		fscanf(IN,"%d%d",&X,&Y);
		Graph[X].push_back(Y);
		Graph[Y].push_back(X);
	}
	
	Get_Back(1,0);
	
	memset(found,0,sizeof found);
		Topological_Sort(1);

	for(int i=N;i>0;i--)
		Get_Low(Sort[i]);
	
	Mark_Edges(1,0);
	
	memset(found,0,sizeof found);
	for(int i=N;i>0;i--)
		Get_BCC(Sort[i]);
	
	fprintf(OUT,"%d\n",Comp);
	for(int i=1;i<=Comp;i++)
	{
		for(int j=0;j<Out[i].size();j++)
			fprintf(OUT,"%d ",Out[i][j]);
		fprintf(OUT,"\n");
	}
    return 0;
}