Cod sursa(job #651124)

Utilizator Robert29FMI Tilica Robert Robert29 Data 19 decembrie 2011 21:25:10
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
FILE*f=fopen("biconex.in","r");
FILE*g=fopen("biconex.out","w");
int j,n,m,x,y,nr,niv1[100004],minniv[100004];
char viz[100001];
vector <int> v[100002];
vector <vector <int> > S;
struct stiva{
	int x,y;
} stv[200002];
inline int min(int a,int b){
	if(a<b)
		return a;
	return b;
}
void dfs(int nod,int father,int niv){
	viz[nod]=1;
	
	niv1[nod]=minniv[nod]=niv;
	
	for(int i=0;i<v[nod].size();++i)
	{
		if(v[nod][i]!=father)
			if(!viz[v[nod][i]])
			{
				stv[++j].x=nod;
				stv[j].y=v[nod][i];
				dfs(v[nod][i],nod,niv+1);
				minniv[nod]=min(minniv[nod],minniv[v[nod][i]]);
				if(minniv[v[nod][i]]>=niv1[nod])
				{
					vector <int> sol;
					do
					{
						sol.push_back (stv[j].x);
						sol.push_back (stv[j].y);
						--j;
					}
					while((stv[j+1].x!=nod||stv[j+1].y!=v[nod][i])&&j>0);
					S.push_back (sol);
					++nr;
				}
			}
			else
				minniv[nod]=min(minniv[nod],niv1[v[nod][i]]);
	}
	
}
int main()
{
	fscanf(f,"%d%d",&n,&m);
	for(int i=1;i<=m;++i)
	{
		fscanf(f,"%d%d",&x,&y);
		v[x].push_back (y);
		v[y].push_back (x);
	}
	
	dfs(1,0,1);
	
	fprintf(g,"%d\n",nr);
	for(int i=0;i<nr;++i){
		S[i].push_back (200000);
		sort(S[i].begin(),S[i].end());
		int nr=S[i].size()-1;
		for(int j=0;j<nr;++j)
			if(S[i][j]!=S[i][j+1])
				fprintf(g,"%d ",S[i][j]);
		fprintf(g,"\n");	
	}
	
	fclose(g);
	fclose(f);
	return 0;
}