Cod sursa(job #686328)

Utilizator iuli1505Parasca Iuliana iuli1505 Data 21 februarie 2012 16:10:27
Problema Componente biconexe Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.49 kb
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
#define nrmaxv 100010
int n,num,nr=1,m,VfS,s[nrmaxv], dfn[nrmaxv], low[nrmaxv];
vector<int> a[nrmaxv],q[nrmaxv];
void citire();
void biconex(int,int);
void initializare();
void afisare();
int main()
{
	freopen("biconex.out","w",stdout);
	citire();
	initializare();
	for(int i=1;i<=n;i++)
		if(!(dfn[i]+1))
			biconex(i,-1);
	printf("%d\n",nr-1);
	afisare();
	return 0;
}
void citire()
{
	freopen("biconex.in","r",stdin);
	scanf("%d%d",&n,&m);
	int x,y,i;
	for(i=1;i<=m;i++)
	{
		scanf("%d%d", &x,&y);
		a[x].push_back(y);
		a[y].push_back(x);
	}
}
void initializare()
{
	int i;
	for(i=1;i<=n;i++)
		dfn[i]=low[i]-1;
	VfS=0;
}
int min(int x, int y)
{
	if(x<y)return x;
	return y;
}
void biconex(int u, int tu)
{
	int x;
	vector<int>::iterator it;
	dfn[u]=low[u]=++num;
	for(it=a[u].begin();it!=a[u].end();it++)
	{
		x=*it;
		if(x!=tu)
		{
			if(dfn[x]==-1)
			{
				s[++VfS]=x;
				s[++VfS]=u;
				biconex(x,u);
				low[u]=min(low[u],low[x]);
				if(low[x]>=dfn[u])
				{
					int i;
					i=VfS;
						while(s[i-1]!=x&&s[i]!=u)
							i-=2;
						i-=1;
						sort(s+i,s+VfS+1);
						q[nr].push_back(s[i]);
						for(int j=i+1;j<=VfS;j++)
							if(s[j]!=s[j-1])
								q[nr].push_back(s[j]);
						nr++;
						VfS=i-1;
					
					
				}
			}
			else
				low[u]=min(low[u],dfn[x]);
		}
	}
}
void afisare()
{
	int i;
	for(i=1;i<nr;i++)
	{
		for(vector<int>::iterator it=q[i].begin();it!=q[i].end();it++)
			printf("%d ", *it);
		printf("\n");
	}
}