Cod sursa(job #383608)

Utilizator Alexa_ioana_14Antoche Ioana Alexandra Alexa_ioana_14 Data 17 ianuarie 2010 11:27:38
Problema Componente biconexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.55 kb
#include<cstdio>
#include<vector>
using namespace std;
#define pb push_back
#define N 100001
#define minn(a,b) ((a<b)? (a):(b))
vector <int> a[N];
int n,m,dep[N],low[N],x,y,st[N][2],rez[100][100],num;
bool viz[N],critic[N];
void citire()
{
	freopen("biconex.in","r",stdin);
	freopen("biconex.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (int i=1; i<=m; ++i)
	{
		scanf("%d%d",&x,&y);
		a[x].pb(y);
		a[y].pb(x);
	}
}
void dfs(int n)
{
	viz[n]=true;
	low[n]=dep[n];
	size_t g=a[n].size();
	for (size_t i=0; i<g; ++i)
	{
		if (!viz[a[n][i]])
		{
			dep[a[n][i]]=1+dep[n];
			st[++st[0][0]][0]=n;
			st[st[0][0]][1]=a[n][i];
			dfs(a[n][i]);
			low[n]=minn(low[a[n][i]],low[n]);
		}
		else
			low[n]=minn(low[n],dep[a[n][i]]);
	}
}
void afis()
{
	printf("%d\n",num);
	for (int i=num-1; i>=0; --i)
	{
		for (int j=rez[i][0]; j; --j)
			printf("%d ",rez[i][j]);
		printf("\n");
	}
	/*for (int i=1; i<=n; ++i)
		printf("%d %d\n",dep[i],low[i]);*/
}
void noduri_critice()
{
	for (int i=1; i<=n; ++i)
	{
		size_t g=a[i].size();
		for (size_t j=0; j<g; ++j)
		{
			if (dep[i]<=low[a[i][j]])
			{
				critic[i]=true;
				break;
			}
		}
	}
}
void noduri()
{
	noduri_critice();
	bool ok=true;
	for (int i=st[0][0]; i;--i)
	{
		if (ok)
			rez[num][++rez[num][0]]=st[i][1];
		if (critic[st[i][0]])
		{
			rez[num][++rez[num][0]]=st[i][0];
			++num;
			
			ok=true;
		}
		else
		{
			rez[num][++rez[num][0]]=st[i][0];
			ok=false;
		}
	}
}
int main()
{
	citire();
	dfs(1);
	noduri();
	afis();
	return 0;
}