Cod sursa(job #720857)

Utilizator ILDottoreBogdan Stoian ILDottore Data 22 martie 2012 23:25:09
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
#include<cstdio>
#include<stack>
#include<vector>
using namespace std;

#define NMAX 100005

FILE *f=fopen("biconex.in","r");
FILE *g=fopen("biconex.out","w");

struct muchie { long x,y;};
stack<muchie> S;
vector<long> L[NMAX],sol[NMAX];

long n,m, nv[NMAX] , mn[NMAX], T[NMAX],viz[NMAX],nr;


void afis(long a,long b)
{   
	nr++;

	while (S.top().x!=a || S.top().y!=b)
	 { sol[nr].push_back(S.top().y);
	   S.pop();
	 }
	sol[nr].push_back(a);
	sol[nr].push_back(b);
    S.pop();
}

void df(long nod)
{
	mn[nod]=nv[nod];
	viz[nod]=1;
	
	for (long i=0;i<L[nod].size();i++)
		if (!viz[ L[nod][i] ] )
			{
				T [ L[nod][i] ] = nod;
				nv[ L[nod][i] ] = nv[nod]+1;
				muchie mc;
				mc.x=nod; mc.y = L[nod][i];
				S.push(mc);
				df( L[nod][i] );
				
				if ( mn[ L[nod][i] ] <mn[nod] ) mn[nod] = mn[L[nod][i]];
				
				if ( mn[ L[nod][i] ] >= nv[nod] ) afis(nod,L[nod][i]);
			}
		else if (nv[ L[nod][i] ] < mn [nod] && L[nod][i]!=T[nod] ) mn[nod]=nv[ L[nod][i] ];
}



int main()
{
	fscanf(f,"%ld%ld",&n,&m);
	
	for (long i=1;i<=m;i++)
	{ long a,b;
	fscanf(f,"%ld%ld",&a,&b);
	L[a].push_back(b);
	L[b].push_back(a);
	}
	
	nv[1]=1;
	df(1);
	
	
	fprintf(g,"%ld\n",nr);
	
	for (long i=1;i<=nr;i++)
	{	for (long j=0;j<sol[i].size();j++)
			fprintf(g,"%ld ",sol[i][j]);
	fprintf(g,"\n");
	}
return 0;}