Cod sursa(job #883826)

Utilizator raulstoinStoin Raul raulstoin Data 20 februarie 2013 13:52:39
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include<fstream>
#include<vector>
#include<algorithm>
#include<stack>
#define NMAX 100005
#define vec G[nod][i]
#define X s.top().first
#define Y s.top().second
using namespace std;
int n,m,lev[NMAX],c;
vector<int> G[NMAX],sol[NMAX];
stack<pair<int,int> > s;
int use[NMAX];
void read()
{
	ifstream fin("biconex.in");
	fin>>n>>m;
	int x,y;
	for(int i=0;i<m;i++)
	{
		fin>>x>>y;
		G[x].push_back(y);
		G[y].push_back(x);
	}
	fin.close();
}
void clear(int x,int y)
{
	while(X!=x && Y!=y)
	{
		sol[c].push_back(Y);
		s.pop();
	}
	sol[c].push_back(y);
	sol[c++].push_back(x);
	s.pop();
}
void DFS(int nod,int TT)
{
	use[nod]=use[TT]+1;
	lev[nod]=use[nod];
	for(size_t i=0;i<G[nod].size();i++)
		if(!use[vec])
		{
			s.push(make_pair(nod,vec));
			DFS(vec,nod);
			lev[nod]=min(lev[nod],lev[vec]);
			if(lev[vec]>=use[nod])
				clear(nod,vec);
		}
		else
			if(vec!=TT)
				lev[nod]=min(lev[nod],lev[vec]);
}
void print()
{
	ofstream fout("biconex.out");
	fout<<c<<'\n';
	for(int i=0;i<c;i++,fout<<'\n')
		for(size_t j=0;j<sol[i].size();j++)
			fout<<sol[i][j]<<' ';
	fout.close();
}
int main()
{
	read();
	s.push(make_pair(1,0));
	DFS(1,0);
	print();
	return 0;
}