Cod sursa(job #530471)

Utilizator ooctavTuchila Octavian ooctav Data 7 februarie 2011 20:57:59
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.7 kb
#include<cstdio>
#include<algorithm>
#include<bitset>
#include<queue>
#include<stack>
#include<vector>
using namespace std;

#define FOR(i, a, b)	for(int i = a ; i <= b ; i++)
#define FORIT(it, V)	for(vector<int> :: iterator it = V.begin() ; it != V.end() ; it++)
#define mp make_pair
#define fs first
#define sc second

const int NMAX = 100005;

int N, M;
vector<int> Graf[NMAX];
int lev[NMAX], jos[NMAX], tata[NMAX];
int viz[NMAX];//fac bitset
stack< pair<int, int> > ST;
int NR;
vector<int> sol[NMAX];

void citi()
{
	scanf("%d%d", &N, &M);
	FOR(i, 1, M)
	{
		int x, y;
		scanf("%d%d", &x, &y);
		Graf[x].push_back(y);
		Graf[y].push_back(x);
	}
}

void dfs(int nod)
{
	viz[nod] = 1;
	jos[nod] = lev[nod] = lev[tata[nod]] + 1;
	FORIT(it, Graf[nod])
		if(!viz[*it])
		{
			tata[*it] = nod;
			ST.push(mp(nod, *it));
			dfs(*it);
			
			jos[nod] = min(jos[nod], jos[*it]);
			
			if(jos[*it] >= lev[nod])
			{
				NR++;
				while(!(ST.top() == mp(nod, *it)))
				{
					sol[NR].push_back(ST.top().fs);
					sol[NR].push_back(ST.top().sc);
					ST.pop();
				}
				sol[NR].push_back(ST.top().fs);
				sol[NR].push_back(ST.top().sc);
				ST.pop();				
			}				
		}
		else if(tata[nod] != *it && lev[*it] < lev[nod])
		{
			jos[nod] = min(jos[nod], lev[*it]);
			ST.push(mp(nod, *it));
		}
}

void scrie()
{
	printf("%d\n", NR);
	FOR(i, 1, N)
	{
		sort(sol[i].begin(), sol[i].end());
		sol[i].resize(unique(sol[i].begin(), sol[i].end()) - sol[i].begin());
		FORIT(it, sol[i])	printf("%d ", *it);
		printf("\n");
	}
}

int main()
{
	freopen("biconex.in", "r", stdin);
	freopen("biconex.out", "w", stdout);
	
	citi();
	dfs(1);
	scrie();
	
	return 0;
}