Cod sursa(job #521901)

Utilizator andrei.dAndrei Diaconeasa andrei.d Data 13 ianuarie 2011 18:55:49
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

#define file_in "biconex.in"
#define file_out "biconex.out"

#define nmax 200102

int niv[nmax];
int viz[nmax];
int v[nmax];
vector<int> G[nmax];
int stiva1[nmax];
int stiva2[nmax];
int nr;
vector<int> sol[nmax];
int n,m,u;


void baga(int a, int b){
	
	int x,y;
	nr++;
	do{
		x=stiva1[u];
		y=stiva2[u--];
		sol[nr].push_back(y);
	}
	while(x!=a || y!=b);
	sol[nr].push_back(x); 
}

void dfs(int nod, int tata){
	
	niv[nod]=niv[tata]+1;
	viz[nod]=1;
	v[nod]=niv[nod];
	
	vector<int> :: iterator it;
	
	for (it=G[nod].begin();it!=G[nod].end();++it){
		
		if (!viz[*it]){
			stiva1[++u]=nod;
			stiva2[u]=*it;
			dfs(*it,nod);
			if (v[*it]<v[nod]) v[nod]=v[*it];
			if (v[*it]>=niv[nod]) baga(nod,*it);
		}
		else{
			if (*it!=tata && v[*it]<v[nod]) v[nod]=v[*it];
		}
	}
}
			

int main(){
	
	int i,a,b,j;	
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
	scanf("%d %d", &n, &m);
	for (i=1;i<=m;++i){
		
		scanf("%d %d", &a, &b);
		
		G[a].push_back(b);
		G[b].push_back(a);
	}
	
	dfs(1,0);
	
	printf("%d\n",nr);
    for(i=1;i<=nr;++i)
    {
		sort(sol[i].begin(),sol[i].end());
        for(j=0;j<sol[i].size();++j)
           printf("%d ",sol[i][j]);
        printf("\n");
    }
    return 0;
}