Cod sursa(job #716930)

Utilizator dicu_dariaDaria Dicu dicu_daria Data 19 martie 2012 13:46:04
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
#include <utility>
#define MAXN 100010
#define mp make_pair
#define f first
#define s second
using namespace std;
stack<pair<int,int> >S;
vector<int>v[MAXN],sol[MAXN];
int viz[MAXN],n,m,comp,sus[MAXN],j;
void dfs(int x)
{
	for(int i=0;i<v[x].size();i++)
	if(!viz[v[x][i]])
	{
		viz[v[x][i]]=viz[x]+1;
		S.push(mp(x,v[x][i]));
		dfs(v[x][i]);
		if(sus[v[x][i]]<sus[x]) sus[x]=sus[v[x][i]];
		if(sus[v[x][i]]>=viz[x]) //gasit
		{
			comp++;
			while(S.top().f!=x or S.top().s!=v[x][i])
			{
				sol[comp].push_back(S.top().s);
				S.pop();
			}
			S.pop();
			sol[comp].push_back(x);
			sol[comp].push_back(v[x][i]);
		}
	} else if(viz[v[x][i]]<sus[x]) sus[x]=viz[v[x][i]];
}
int main()
{
	int i,x,y;
	ifstream fi("biconex.in");
	ofstream fo("biconex.out");
	fi>>n>>m;
	for(i=1;i<=m;i++)
	{
		fi>>x>>y;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	viz[1]=1;
	for(i=1;i<=n;i++) sus[i]=int(2e9);
	dfs(1);
	fo<<comp<<"\n";
	for(i=1;i<=comp;i++)
	{
		sort(sol[i].begin(),sol[i].end());
		for(j=0;j<sol[i].size();j++) fo<<sol[i][j]<<" ";
		fo<<"\n";
	}
	return 0;
}