Cod sursa(job #575375)

Utilizator mihaipopa12Popa Mihai mihaipopa12 Data 8 aprilie 2011 11:22:25
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.75 kb
#include<stdio.h>
#include<vector>

#define maxN 100005

using namespace std;

FILE*f=fopen("biconex.in","r");
FILE*g=fopen("biconex.out","w");

vector<int>G[maxN]; vector< pair<int,int> >Stv;
vector<int>CompB[maxN];

int i,m,n,Viz[maxN],x,y; int Vf,niv[maxN],lowest[maxN];
int Nrcomp,j;

inline void citire () {
	
	fscanf(f,"%d %d",&n,&m);
	
	for ( i = 1 ; i <= m ; ++i ){
		
		fscanf(f,"%d %d",&x,&y);
		
		G[x].push_back(y);
		G[y].push_back(x);
		
	}
	
}

void componenta (int nod,int fiu) {
	int x,y;
	
	++Nrcomp;
	
	do{
		x = Stv[Vf].first , y = Stv[Vf].second;
		--Vf; Stv.pop_back();
		CompB[Nrcomp].push_back(y);
		
	}while ( x != nod && y != fiu );
	
	CompB[Nrcomp].push_back(nod);
	
}

void dfs( int nod , int tata ) {
	
	Viz[nod] = 1; lowest[nod] = niv[tata] + 1; niv[nod] = niv[tata] + 1;
	
	for ( int i = 0 ; i < G[nod].size() ; ++i ){
		
		int nodvcn = G[nod][i];
		
		if ( nodvcn != tata ){
			if ( !Viz[nodvcn] ){
				
				++Vf;
				Stv.push_back(make_pair(nod,nodvcn));
				
				dfs(nodvcn,nod);
				
				if  ( lowest[nodvcn] >= niv[nod] )
					componenta(nod,nodvcn);
				
				if ( lowest[nodvcn] < lowest[nod] )
					lowest[nod] = lowest[nodvcn];
				
			}
			else{
				if ( lowest[nod] > niv[nodvcn] )
					lowest[nod] = niv[nodvcn];
			}
		}
		
	}
	
}

inline void afisare () {
	
	vector<int>::iterator itt;
	
	fprintf(g,"%d\n",Nrcomp);
	
	for ( i = 1 ; i <= Nrcomp ; ++i ){
		for ( itt = CompB[i].begin(); itt != CompB[i].end() ; ++itt ){
			fprintf(g,"%d ",*itt);
		}
		fprintf(g,"\n");
	}
	
}

int main () {
	
	citire();
	
	Vf = -1;
	
	for ( i = 1 ; i <= n ; ++i ){
		if ( !Viz[i] )
			dfs(i,0);
	}
	
	afisare();
	
	fclose(f);
	fclose(g);
	
	return 0;
}