Cod sursa(job #937720)

Utilizator veleanduAlex Velea veleandu Data 10 aprilie 2013 22:04:05
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#include <cassert>
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#include <stack>
using namespace std;

#define FORIT( it,v ) for( typeof((v).begin()) it=(v).begin(); it!=(v).end(); ++it )

const int max_n=100005;

vector<int> Vertex[max_n], Comp[max_n];
int n, m, a, b, i;
int nrComp;

int Deep[max_n], Low[max_n];
stack<int> Stack;

void get_min( int &a, int b ){
	if( a>b )
		a=b;
}

void df( int nod, int deep ){
	if( Deep[nod] )
		return ;
	Deep[nod]=deep;
	Low[nod]=deep;
	Stack.push(nod);
	FORIT( it, Vertex[nod] ){
		if( !Deep[*it] ){
			df( *it, deep+1 );
			get_min( Low[nod], Low[*it] );
			if( Low[*it] == deep ){
				bool ok=1;
				nrComp++;
				Comp[nrComp].push_back(nod);
				while( ok ){
					Comp[nrComp].push_back( Stack.top () );
					if( Stack.top() == *it )
						ok=0;
					Stack.pop();
				}
			}
		}
		get_min( Low[nod], Deep[*it] );
	}
	return ;
}

int main(){
	assert(freopen("biconex.in","r",stdin));
	assert(freopen("biconex.out","w",stdout));
	scanf("%d %d", &n, &m);
	for( ; m--; ){
		scanf("%d %d", &a, &b );
		Vertex[a].push_back( b );
		Vertex[b].push_back( a );
	}
	df( 1,1 );
	printf("%d\n",nrComp);
	for( i=1; i<=nrComp; ++i, printf("\n") ){
		sort( Comp[i].begin(), Comp[i].end() );
		FORIT( it, Comp[i] )
			printf("%d ", *it );
	}
	return 0;
}