Cod sursa(job #631802)

Utilizator DaicuDaicu Alexandru Daicu Data 9 noiembrie 2011 19:42:51
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.56 kb
#include<stdio.h>
#include<vector>
#include<stack>
#include<set>
#include<algorithm>
#define nmax 100003 
#define min(x,y) x<y ? x:y 
using namespace std;
vector <int> graf[nmax];
stack < pair <int,int> > st;
vector <vector <int> > comp_bicx;
int n,m,sel[nmax],lvl[nmax],lvl_back[nmax];

void read(){
	scanf("%d%d",&n,&m);
	int x,y;
	for(int i=1;i<=m;i++){
		scanf("%d%d",&x,&y);
		graf[x].push_back(y);
		graf[y].push_back(x);
	}
}

void compconex(int x,int y){
	vector <int> ncomp;
	int cx,cy;
	cx=st.top().first;
	cy=st.top().second;
	if(cx==x && cy==y){
		ncomp.push_back(cx);
		ncomp.push_back(cy);
		st.pop();
	}
	else{
		
		
	while(cx!=x && cy!=y){
		cx=st.top().first;
		cy=st.top().second;
		ncomp.push_back(cy);
		st.pop();
	}
	ncomp.push_back(cx);
	}
	comp_bicx.push_back(ncomp);
}
		

void df(int x,int f,int niv){
	sel[x]=1;
	lvl[x]=lvl_back[x]=niv;
	for(unsigned int i=0;i<graf[x].size();i++){
		if(!sel[graf[x][i]]){
			st.push(make_pair(x,graf[x][i]));
			df(graf[x][i],x,niv+1);
			lvl_back[x]=min(lvl_back[x],lvl_back[graf[x][i]]);
			if(lvl_back[graf[x][i]]>=lvl[x])
				compconex(x,graf[x][i]);
		}
		else
			lvl_back[x]=min(lvl_back[x],lvl[graf[x][i]]);
	}
}

int main()
{freopen("biconex.in","r",stdin);
freopen("biconex.out","w",stdout);
read();
df(1,0,0);
printf("%d\n",comp_bicx.size());
for(unsigned int i=0;i<comp_bicx.size();i++){
	sort(comp_bicx[i].begin(),comp_bicx[i].end());
	for(unsigned int j=0;j<comp_bicx[i].size();j++)
		printf("%d ",comp_bicx[i][j]);
	printf("\n");
}
return 0;
}