Cod sursa(job #296038)

Utilizator andrei-alphaAndrei-Bogdan Antonescu andrei-alpha Data 4 aprilie 2009 00:44:04
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.87 kb
using namespace std;

#include <set>
#include <map>
#include <list>
#include <deque>
#include <stack>
#include <queue>
#include <cmath>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <utility>
#include <algorithm>

#define pb push_back
#define sz size
#define f first
#define s second
#define II inline
#define ll long long
#define db double
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define all(v) v.begin() , v.end()
#define CC(v) memset((v),0,sizeof((v)))
#define CP(v,w) memcpy((v),(w),sizeof((w)))
#define mp make_pair

#define IN  "biconex.in"
#define OUT "biconex.out"
#define N_MAX 1<<17

typedef vector<int> VI;
typedef pair<int,int> pi;
typedef vector<string> VS;

int rez,size,N,M,T[N_MAX],H[N_MAX],C[N_MAX];
vector<int> A[N_MAX],Sol[N_MAX];
vector<pi> S(1<<18);
vector<bool> viz(N_MAX);

II void scan()
{
	freopen(IN,"r",stdin);
	freopen(OUT,"w",stdout);
	
	int x,y;
	scanf("%d%d",&N,&M);
	FOR(i,1,M)
	{
		scanf("%d%d",&x,&y);
		A[x].pb(y);
		A[y].pb(x);
	}
	H[1] = viz[1] = 1; 
}


II void DF(int nod)
{
	C[nod] = H[nod];
	vector<int>::iterator it;
	for(it=A[nod].begin();it != A[nod].end();++it)
	{
		int fiu = *it;
		if(viz[fiu])
		{
			if(fiu != T[nod])
				C[nod] = min(C[nod],H[fiu]);
			continue;
		}
		viz[fiu] = true;
		
		S[++size] = mp(nod,fiu);
		T[fiu] = nod;
		H[fiu] = H[nod] + 1;
		DF(fiu);
		
		C[nod] = min(C[nod],C[fiu]);
	
	}
	if(C[nod] >= H[ T[nod] ] && size)
	{
		++rez;
		for(;S[size] != mp(T[nod],nod) && size;Sol[rez].pb( S[size--].s ) );
		Sol[rez].pb( S[size--].s );
		Sol[rez].pb( T[nod] );
	}
}

II void print()
{
	printf("%d\n",rez);
	FOR(i,1,rez)
	{
		vector<int>::iterator it;
		for(it = Sol[i].end()-1;it != Sol[i].begin()-1;--it)
			printf("%d ",*it);
		printf("\n");
	}	
}

int main()
{
	scan();
	DF(1);
	print();
	return 0;
}