Cod sursa(job #471704)

Utilizator tamas_iuliaTamas Iulia tamas_iulia Data 20 iulie 2010 14:19:07
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
#include <stdio.h>
#include <vector>
#include <stack>
#include <set>
#define Nmax 100005
#define Mmax 200005
#define pb push_back
#define mp make_pair
#define x first
#define y second
using namespace std;

vector< int > v[Nmax];
stack< pair<int,int> > S;
vector< set< int > > Cb;
int dfn[Nmax],low[Nmax];
int n,m,nr=0;

inline int Minim(int x,int y){ return x<y ? x:y; }

void comp_bicon(int u,int tu){
	set< int > aux;
	pair< int, int > p;
	do{
		p=S.top(); S.pop();
		aux.insert(p.x); aux.insert(p.y);
	} while( p.x != tu && p.y!=u);
	Cb.pb(aux);
}

void Df(int u, int tu){
	vector< int >:: iterator it;
	dfn[u]=low[u]=++nr;
	
	for(it=v[u].begin(); it!=v[u].end(); ++it){
		if( *it==tu ) continue;
		if( dfn[*it]==-1 ){
			S.push(mp(u,*it));
			Df(*it,u);
			low[u]=Minim(low[u],low[*it]);
			
			if( low[*it] >= dfn[u] )
				comp_bicon(*it,u);
		}
		else
			low[u]=Minim(low[u],dfn[*it]);
	}
}

int main(){
	int i,x,y;
	set< int >:: iterator sit;

	freopen("biconex.in","r",stdin);
	freopen("biconex.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;++i){
		scanf("%d%d",&x,&y);
		v[x].pb(y);
		v[y].pb(x);
	}
	
	for(i=1;i<=n;++i) dfn[i]=low[i]=-1;
	Df(1,0);
	
	printf("%d\n",Cb.size());
	for(size_t it=0; it<Cb.size(); ++it){
		for( sit=Cb[it].begin(); sit!=Cb[it].end(); ++sit)
			printf("%d ",*sit);
		printf("\n");
	}
	
	fclose(stdin); fclose(stdout);
	return 0;
}