Cod sursa(job #530298)

Utilizator hadesgamesTache Alexandru hadesgames Data 7 februarie 2011 14:32:49
Problema Componente biconexe Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.67 kb
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair

FILE *in,*out;
pair<int,int> stiva[100500];
vector<int> rez[300500],a[100500];
int v[100500],adanc[100500],low[100500];
int nrrez,u;
const int inf=1<<30;
inline int minim(int a, int b)
{
	return a<b?a:b;
}
int dfs(int x,int adancime)
{
	int i,lastu,tatal;
	v[x]=2;
	//printf("Intra %d\n",x);
	adanc[x]=adancime;
	low[x]=adancime;
	tatal=stiva[u].fi;
	for (i=0;i<a[x].size();i++)
		if (!v[a[x][i]])
		{
			u++;
			stiva[u]=mp(x,a[x][i]);
			lastu=u;
			dfs(a[x][i],adancime+1);
			low[x]=min(low[x],low[a[x][i]]);
			if (low[a[x][i]]>=adanc[x])
			{
				nrrez++;
		//		printf("%d %d\n",u,lastu);
				for (;u>=lastu;u--)
				{
	//				printf("%d (%d %d)\n",nrrez,stiva[u].fi,stiva[u].se);
					rez[nrrez].pb(stiva[u].se);
				}
					
			}
		}
		else if ( v[a[x][i]]==2)
		{
			u++;
			stiva[u]=mp(x,a[x][i]);
			if (tatal!=a[x][i])
				low[x]=min(low[x],adanc[a[x][i]]);
		}
//	printf("Iese %d %d %d \n",x,adanc[x],low[x]);
	v[x]=1;
}
int main()
{
	int n,m,x,y,i,j;
	vector<int>::iterator jt,end;
	in=fopen("biconex.in","r");
	out=fopen("biconex.out","w");
	fscanf(in,"%d%d",&n,&m);
	for (i=1;i<=m;i++)
	{
		fscanf(in,"%d%d",&x,&y);
		a[x].pb(y);
		a[y].pb(x);
	}
	for (i=1;i<=n;i++)
		if (!v[i])
			dfs(i,1);
	
	fprintf(out,"%d\n",nrrez);
	for (i=1;i<=nrrez;i++)
	{
		sort(rez[i].begin(),rez[i].end());
		end=unique(rez[i].begin(),rez[i].end());
		for (jt=rez[i].begin();jt!=end;jt++)
			fprintf(out,"%d ",*jt);
		fprintf(out,"\n");
	}
	fclose(in);
	fclose(out);
	return 0;
}