Cod sursa(job #1948710)

Utilizator GabiTulbaGabi Tulba-Lecu GabiTulba Data 1 aprilie 2017 12:51:51
Problema Componente biconexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 2.2 kb
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#define MaxN 1005
#define node 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;
bool found[MaxN];
queue<int>Q;
vector<int> Graph[MaxN],Back[MaxN],Out[MaxN];
vector<pair<int,int> >T[MaxN];
void Get_Back(int node,int father)
{
	found[node]=true;
	Father[node]=father;
	Low[node]=node;
	for(int i=0;i<Graph[node].size();i++)
	{
		if(!found[Graph[node][i]])
			Get_Back(Graph[node][i],node),T[node].push_back(make_pair(Graph[node][i],-1));
		else if(Graph[node][i]!=Father[node])Back[node].push_back(Graph[node][i]);
	}
}
void Get_Low(int node)
{
	int L=Low[node];
	for(int i=0;i<Back[node].size();i++)
		if(Low[Back[node][i]]!=L)Q.push(Back[node][i]);
	while(!Q.empty())
	{
		if(Low[Q.front()]!=L)
			Low[Q.front()]=L,Q.push(Father[Q.front()]);
		Q.pop();
		
	}
}
void Mark_Edges(int node,int C)
{
	for(int i=0;i<T[node].size();i++)
	{
		if(Low[T[node][i].node]==Low[Father[node]])
		{
			T[node][i].colour=C;
			Mark_Edges(T[node][i].node,C);
		}
		else
		{
			T[node][i].colour=++Colour;
			Mark_Edges(T[node][i].node,Colour);
		}
	}
}
void Get_Comp(int node,int C)
{
	Out[Comp].push_back(node);
	for(int i=0;i<T[node].size();i++)
		if(T[node][i].colour==C)
			Get_Comp(T[node][i].node,C);
}
void Get_BCC(int node)
{
	for(int i=0;i<T[node].size();i++)
		if(!found[T[node][i].colour])
		{
			found[T[node][i].colour]=true;
			Out[++Comp].push_back(node);
			Get_Comp(T[node][i].node,T[node][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);
	
	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;
}