Cod sursa(job #558150)

Utilizator Bogdan_tmmTirca Bogdan Bogdan_tmm Data 17 martie 2011 09:29:44
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
#include <algorithm>
#include <vector>
#include <stack>
#include <set>
using namespace std;

#define N_MAX 100005
typedef pair <int,int> p;

set <int> bc[N_MAX];
int nrBc;

vector <int> a[N_MAX];

int n,m,i,j,x,y;

int NR=1;

int low[N_MAX],up[N_MAX];
int tata[N_MAX];

stack <p> ST;

void cBc(int x,int y)
{
    int _X, _Y;
	nrBc++;
    do
	{
        _X = ST.top().first;
		_Y = ST.top().second;
		
        ST.pop();
		
        bc[nrBc].insert(_X);
		bc[nrBc].insert(_Y);
    }while (_X != x || _Y != y);
}

void df(int nod)
{
	low[nod]=NR;
	up[nod]=NR;
	NR++;
	
	vector <int> ::iterator it;
	
	for(it=a[nod].begin();it!=a[nod].end();it++)
	{
		if(low[*it]==0)
		{
			ST.push(p(nod,*it));
			tata[*it]=nod;
			
			df(*it);
			
			low[nod]=min(low[nod],low[*it]);
			
			if(up[nod]<=low[*it])
				cBc(nod,*it); 
		}
		else
		{
			if(tata[nod]!=*it)
				low[nod]=min(low[nod],low[*it]);
		}
		
	}
}

int main()
{
	freopen("biconex.in","r",stdin);
	freopen("biconex.out","w",stdout);
	
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;i++)
	{
		scanf("%d%d",&x,&y);
		a[x].push_back(y);
		a[y].push_back(x);
	}
	
	df(1);
	
	printf("%d\n",nrBc);
	for(i=1;i<=nrBc;i++)
	{
		set <int> ::iterator it;
		for(it=bc[i].begin();it!=bc[i].end();it++)
			printf("%d ",*it);
		printf("\n");
	}
	return 0;
}