Cod sursa(job #633450)

Utilizator swift90Ionut Bogdanescu swift90 Data 13 noiembrie 2011 20:02:46
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
#include<cstdio>
#include<vector>
#include<stack>
#include<algorithm>
using namespace std;
int N,M;
typedef pair<int,int> PII;
stack<PII> S;
vector<int> nr[100100];
vector<vector<int> > CB;
int tata[100100],low[100100],dfn[100100];
inline int min(int a,int b){
	return a<b?a:b;
}
void CBC(int x,int y){
	vector<int> aux;
	int sx,sy;
	do{
		sx=S.top().first;
		sy=S.top().second;
		S.pop();
		aux.push_back(sx);
		aux.push_back(sy);
	}while(sx!=x || sy!=y);
	sort(aux.begin(),aux.end());
	aux.erase(unique(aux.begin(),aux.end()),aux.end());
	CB.push_back(aux);
}
void df(int x,int ad){
	dfn[x]=low[x]=ad;
	for(vector<int>::iterator it=nr[x].begin();it!=nr[x].end();++it){
		if(*it==tata[x])
			continue;
		if(dfn[*it]==-1){
			tata[*it]=x;
			S.push(PII(x,*it));
			df(*it,ad+1);
			low[x]=min(low[x],low[*it]);
			if(low[*it]>=dfn[x])
				CBC(x,*it);
		}
		else
			low[x]=min(low[x],dfn[*it]);
	}
}
int main(){
	freopen("biconex.in","r",stdin);
	freopen("biconex.out","w",stdout);
	int i,x,y;
	scanf("%d%d",&N,&M);
	for(i=0;i<M;++i){
		scanf("%d%d",&x,&y);
		nr[x].push_back(y);
		nr[y].push_back(x);
	}
	for(i=1;i<=N;++i)
		dfn[i]=-1;
	df(1,0);
	printf("%d\n",CB.size());
	for(i=0;i<(int)CB.size();++i){
		for(vector<int>::iterator it=CB[i].begin();it!=CB[i].end();++it)
			printf("%d ",*it);
		printf("\n");
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}