Cod sursa(job #604744)

Utilizator crushackPopescu Silviu crushack Data 24 iulie 2011 20:38:21
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.38 kb
#include <stdio.h>
#include <algorithm>
#include <vector>
#define NMax 100010
using namespace std;

const char IN[]="biconex.in",OUT[]="biconex.out";

int N,M;
int lvl[NMax],low[NMax];
vector<int> ad[NMax];
vector<pair<int,int> > v;
vector<vector<int> > Sol;

void upd(int x,int y)
{
	vector<int> c;
	int tx,ty;
	do{
		tx=(v.end()-1)->first;ty=(v.end()-1)->second;
		v.pop_back();
		c.push_back(tx);c.push_back(ty);
	}
	while (tx!=x || ty!=y);
	Sol.push_back(c);
}

void bfs(int x=1,int p=0,int lv=1)
{
	lvl[x]=low[x]=lv;
	for (vector<int>::iterator it=ad[x].begin();it!=ad[x].end();++it) 
	{
		if (p==*it) continue;
		if (!lvl[*it])
		{
			v.push_back(make_pair(x,*it));
			bfs(*it,x,lv+1);
			low[x]= min(low[x],low[*it]);
			
			if (low[*it]>=lvl[x])
				upd(x,*it);
		}
		else
			low[x]= min(low[x],lvl[*it]);
	}
}

int main()
{
	int x,y;
	freopen(IN,"r",stdin);
	scanf("%d%d",&N,&M);
	while (M--)
		scanf("%d%d",&x,&y),
		ad[x].push_back(y),
		ad[y].push_back(x);
	fclose(stdin);
	
	bfs();
	
	freopen(OUT,"w",stdout);
	printf("%d\n",Sol.size());
	for (int i=0;i<(int)Sol.size();++i)
	{
		sort(Sol[i].begin(),Sol[i].end());
		Sol[i].erase(unique(Sol[i].begin(),Sol[i].end()),Sol[i].end());
		for (typeof(Sol[i].begin()) it2=Sol[i].begin();it2<Sol[i].end();++it2)
			printf("%d ",*it2);
		printf("\n");
	}
	fclose(stdout);
	return 0;
}