Cod sursa(job #540690)

Utilizator siminescuPaval Cristi Onisim siminescu Data 24 februarie 2011 11:31:05
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.38 kb
#include<fstream>
#include<stack>
#include<vector>
#include<iterator>
#include<algorithm>
using namespace std;

ifstream f("biconex.in");
ofstream g("biconex.out");

# define nmax 100002
# define Min(a,b) ((a)<(b)? (a):(b))

vector <int> v[nmax];
vector <vector <int> > afis;
stack <pair <int,int> > S;
int N,M,niv[nmax],low[nmax];

void citire()
{
	f>>N>>M;
	int i,j;
	for(;M;--M)
		f>>i>>j, v[i].push_back(j), v[j].push_back(i);
}
void componenta(int a,int b)
{
	int x,y;
	vector <int> c;
	do{
		x=S.top().first; y=S.top().second;
		S.pop();
		c.push_back(x); c.push_back(y);
	}while(x!=a||y!=b);
	afis.push_back(c);
}
void cbc(int nod,int nivel,int parinte)
{
	niv[nod]=low[nod]=nivel;
	vector <int>::const_iterator it;
	for(it=v[nod].begin();it<v[nod].end();++it)
	{
		if(*it==parinte) continue;
		if(niv[*it])
			low[nod]=Min(low[nod],niv[*it]);
		else
		{
			S.push(make_pair(nod,*it));
			cbc(*it,nivel+1,nod);
			low[nod]=Min(low[nod],low[*it]);
			if(low[*it]>=niv[nod])
				componenta(nod,*it);
		}
	}
}
int main()
{
	citire();
	int i,n,m,j,x;
	for(i=1;i<=N;++i)
		if(!niv[i])
			cbc(1,1,-1);
	n=afis.size();
	for(i=0;i<n;++i) sort(afis[i].begin(),afis[i].end());
	g<<n<<'\n';
	for(i=0;i<n;++i)
	{
		m=afis[i].size();
		x=0;
		for(j=0;j<m;++j)
			if(afis[i][j]!=x)
				g<<afis[i][j]<<' ', x=afis[i][j];
		g<<'\n';
	}
	return 0;
}