Cod sursa(job #1948746)

Utilizator GabiTulbaGabi Tulba-Lecu GabiTulba Data 1 aprilie 2017 13:13:20
Problema Componente biconexe Scor 18
Compilator cpp Status done
Runda Arhiva educationala Marime 2.35 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];
bool found[MaxN];
queue<int>Q;
vector<int> Graph[MaxN],Back[MaxN],Out[MaxN];
vector<pair<int,int> >T[MaxN];
void Get_Back(int vertex,int father,int depth)
{
	Depth[vertex]=depth;
	found[vertex]=true;
	Father[vertex]=father;
	Low[vertex]=vertex;
	for(int i=0;i<Graph[vertex].size();i++)
	{
		if(!found[Graph[vertex][i]])
			Get_Back(Graph[vertex][i],vertex,depth+1),T[vertex].push_back(make_pair(Graph[vertex][i],-1));
		else if(Depth[vertex]+1<Depth[Graph[vertex][i]])Back[vertex].push_back(Graph[vertex][i]);
	}
}
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)
{
	for(int i=0;i<T[vertex].size();i++)
	{
		if(Low[T[vertex][i].vertex]==Low[Father[vertex]])
		{
			T[vertex][i].colour=C;
			Mark_Edges(T[vertex][i].vertex,C);
		}
		else
		{
			T[vertex][i].colour=++Colour;
			Mark_Edges(T[vertex][i].vertex,Colour);
		}
	}
}
void Get_Comp(int vertex,int C)
{
	Out[Comp].push_back(vertex);
	for(int i=0;i<T[vertex].size();i++)
		if(T[vertex][i].colour==C)
			Get_Comp(T[vertex][i].vertex,C);
}
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,1);
	
	for(int i=1;i<=N;i++)
		Get_Low(i);
	
	Mark_Edges(1,0);
	
	memset(found,0,sizeof found);
	for(int i=1;i<=N;i++)
		Get_BCC(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;
}