Cod sursa(job #414980)

Utilizator al_flAlexandru Flavian al_fl Data 10 martie 2010 19:36:30
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
#include <cstdio>
#include <vector>

using namespace std;

#define file_in "biconex.in"
#define file_out "biconex.out"

#define Nmax 221000

int n,m;
vector<int> G[Nmax];
vector<int> s[Nmax];
int viz[Nmax];
int sol;
int vf,nr;
int st[Nmax];
int low[Nmax];
int dfn[Nmax];

inline int min(int a, int b) { return a<b?a:b; }

void add(int x, int y)
{
	sol++;
	do
	{
		s[sol].push_back(st[--vf]);
		s[sol].push_back(st[--vf]);
	}
	while(st[vf+1]!=y || st[vf]!=x);
}

void dfs(int nod)
{
	viz[nod]=1;

	low[nod]=dfn[nod]=++nr;

	for (int i=0;i<G[nod].size();++i)
	{
		int x=G[nod][i];
		if (!viz[x])
		{
			st[vf++]=nod;
			st[vf++]=x;
			dfs(x);
			if (low[x]>=dfn[nod])
				add(nod,x);
			low[nod]=min(low[nod],low[x]);
		}
		else
			low[nod]=min(low[nod],dfn[x]);
	}
}


int main()
{
	int a,b,i,j;
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);

	scanf("%d %d", &n, &m);

	for (i=1;i<=m;++i)
	{
		scanf("%d %d", &a, &b);

		G[a].push_back(b);
		G[b].push_back(a);
	}

	for (i=1;i<=n;++i)
		 if (!viz[i])
			 dfs(i);

	printf("%d\n", sol);

	for (i=1;i<=sol;++i)
	{
		for (j=0;j<s[i].size();++j)
		{
			int x=s[i][j];
			viz[x]=0;
		}
		for (j=0;j<s[i].size();++j)
			 if (viz[s[i][j]]==0)
			 {
				 viz[s[i][j]]=1;
				 printf("%d ", s[i][j]);
			 }
		printf("\n");
	}

	fclose(stdin);
	fclose(stdout);

	return 0;

}