Cod sursa(job #327253)

Utilizator AndreyPAndrei Poenaru AndreyP Data 27 iunie 2009 19:23:03
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 kb
#include<stdio.h>
#include<vector>
#include<stack>
#include<algorithm>
using namespace std;
#define pb push_back
#define fs first
#define sc second
#define mp make_pair
#define N 100010
int n;
vector<int> a[N],dfn,low;
vector< vector<int> > rez;
stack< pair<int,int> > st;
inline void citire()
{
	int m,x,y;
	scanf("%d%d",&n,&m);
	for(int i=0; i<m; ++i)
	{
		scanf("%d%d",&x,&y);
		a[x].pb(y);
		a[y].pb(x);
	}
	dfn.assign(n+1,-1);
	low.resize(n+1);
}
inline void extrag(int x,int y)
{
	vector<int> con;
	int tx,ty;
	do
	{
		tx=st.top().fs;
		ty=st.top().sc;
		st.pop();
		con.pb(tx);
		con.pb(ty);
	}while(tx!=x || ty!=y);
	rez.pb(con);
}
void dfs(int nod,int fn,int num)
{
	dfn[nod]=low[nod]=num;
	for(size_t i=0,lim=a[nod].size(); i<lim; ++i)
	{
		if(a[nod][i]==fn)
			continue;
		if(dfn[a[nod][i]]==-1)
		{
			st.push(mp(nod,a[nod][i]));
			dfs(a[nod][i],nod,num+1);
			low[nod]=min(low[a[nod][i]],low[nod]);
			if(low[a[nod][i]]>=dfn[nod])
				extrag(nod,a[nod][i]);
		}
		else
			low[nod]=min(low[nod],dfn[a[nod][i]]);
	}
}
int main()
{
	freopen("biconex.in","r",stdin);
	freopen("biconex.out","w",stdout);
	citire();
	dfs(1,0,0);
	printf("%u\n",rez.size());
	for(size_t i=0,lim=rez.size(); i<lim; ++i)
	{
		sort(rez[i].begin(),rez[i].end());
		rez[i].erase(unique(rez[i].begin(),rez[i].end()),rez[i].end());
		for(size_t j=0,lim1=rez[i].size(); j<lim1; ++j)
			printf("%d ",rez[i][j]);
		printf("\n");
	}
	return 0;
}