Cod sursa(job #521610)

Utilizator AndreyPAndrei Poenaru AndreyP Data 12 ianuarie 2011 22:41:27
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.64 kb
#include <cstdio>
#include <stack>
#include <bitset>
#include <algorithm>
#include <vector>
using namespace std;
#define N 100010
#define fs first
#define sc second
#define mp make_pair
#define pii pair< int,int >
#define pb push_back
template< class T >
inline T minim(const T &x,const T &y) {
	return ( (x<y) ? x : y );
}

int n;
vector< int > a[N];
int ind[N],indlow[N],indice;
stack< int > st;
vector< vector< int > > bicon;
int nrez;
bitset< N > viz;

inline void citire() {
	int m,x,y;
	scanf("%d%d",&n,&m);
	for(int i=0; i<m; ++i) {
		scanf("%d%d",&x,&y);
		a[x].pb(y);
		a[y].pb(x);
	}
}

void dfs(int nod,int tata) {
	++indice;
	ind[nod] = indlow[nod] = indice;

	int nod1;
	for(size_t i=0,lim=a[nod].size(); i<lim; ++i) {
		nod1 = a[nod][i];
		if(nod1==tata)
			continue;
		if(ind[nod1]==0) {
			st.push(nod);
			dfs(nod1,nod);
			indlow[nod] = minim(indlow[nod1],indlow[nod]);

			if(indlow[nod1]>=ind[nod]) {
				bicon.resize(nrez+1);
				do {
					nod1 = st.top();
					st.pop();
					bicon[nrez].pb(nod1);
				}while(nod1!=nod);
				++nrez;
			}
		} else
			indlow[nod] = minim(indlow[nod],indlow[nod1]);
	}
	st.push(nod);
}

inline void scrie() {
	printf("%d\n",nrez);
	for(int i=0; i<nrez; ++i) {
		viz.reset();
		for(size_t j=0,lim=bicon[i].size(); j<lim; ++j) {
			if(viz[bicon[i][j]]==1)
				continue;
			viz[bicon[i][j]] = 1;
			printf("%d ",bicon[i][j]);
		}
		printf("\n");
	}
}

int main() {
	freopen("biconex.in","r",stdin);
	freopen("biconex.out","w",stdout);

	citire();
	for(int i=1; i<=n; ++i) {
		if(ind[i]!=0)
			continue;
		dfs(i,0);
	}
	scrie();

	return 0;
}