Cod sursa(job #434084)

Utilizator borsoszalanBorsos Zalan borsoszalan Data 5 aprilie 2010 00:02:32
Problema Componente biconexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
#include<stdio.h>
#include<vector>
#include<stack>
#define nmax 100004

using namespace std;

int n,m,i,j,nr,aux;
int level[nmax], back[nmax], vis[nmax];
vector<int> g[nmax];
vector<int> sol[nmax];
stack<pair<int, int> > st;


void read()
{
	freopen("biconex.in","r",stdin);
    freopen("biconex.out","w",stdout);
    int x,y;
    scanf("%d %d ",&n,&m);
    for(int i=1;i<=m;++i)
    {
        scanf("%d %d",&x,&y);
        g[x].push_back(y);
        g[y].push_back(x);
    }
}

void write()
{
	printf("%d\n", nr);
	for(i=1;i<=nr;i++)
	{
		for(j=0;j<sol[i].size();j++)
			printf("%d ", sol[i][j]);
		printf("\n");
	}
}

void add(int dad, int son)
{
	nr++;
	sol[nr].push_back(st.top().second);
	sol[nr].push_back(st.top().first);
	st.pop();
	for(;!st.empty()&&(st.top().first!=dad||st.top().second!=son);st.pop())
		sol[nr].push_back(st.top().first);
	sol[nr].push_back(st.top().first);
	st.pop();
}

void bfs(int nod, int dad)
{
	level[nod]=level[dad]+1;
	back[nod]=level[nod];
	vis[nod]=1;
	int i,aux;
	for(i=0;i<g[nod].size();i++)
	{
		aux=g[nod][i];
		if(!vis[aux])
		{
			st.push(make_pair(nod, aux));
			bfs(aux, nod);
			if(back[aux]<back[nod])
				back[nod]=back[aux];
			if(back[aux]>=level[nod])
				add(nod, aux);
		}
		else if(aux!=nod&&back[aux]<back[nod])
			back[nod]=back[aux];
	}
}

				




int main()
{
	read();
	bfs(1, 0);
	write();
	return 0;
}