Cod sursa(job #575412)

Utilizator ChallengeMurtaza Alexandru Challenge Data 8 aprilie 2011 11:57:47
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.56 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

const char InFile[]="biconex.in";
const char OutFile[]="biconex.out";
const int MaxN=100111;

ifstream fin(InFile);
ofstream fout(OutFile);

struct s_edge
{
	s_edge(int _x=0, int _y=0):x(_x),y(_y){}
	int x,y;
};

int N,M,x,y,nrcomponente,niv[MaxN],low[MaxN];
vector<int> G[MaxN];
vector< vector<int> > C;
stack<s_edge> S;

void componenta(int x, int y)
{
	vector<int> comp;
	int tx,ty;
	do
	{
		tx=S.top().x;
		ty=S.top().y;
		S.pop();
		comp.push_back(ty);
	}while(x!=tx || y!=ty);
	comp.push_back(x);
	C.push_back(comp);
}

void DFS(int nod, int tata)
{
	niv[nod]=low[nod]=niv[tata]+1;
	for(vector<int>::iterator it=G[nod].begin();it!=G[nod].end();++it)
	{
		if(*it==tata)
		{
			continue;
		}
		if(!niv[*it])
		{
			S.push(s_edge(nod,*it));
			DFS(*it,nod);
			low[nod]=min(low[nod],low[*it]);
			if(low[*it]>=niv[nod])
			{
				componenta(nod,*it);
			}
		}
		else
		{
			low[nod]=min(low[nod],niv[*it]);
		}
	}
}

int main()
{
	fin>>N>>M;
	for(register int i=1;i<=M;++i)
	{
		fin>>x>>y;
		G[x].push_back(y);
		G[y].push_back(x);
	}
	fin.close();
	
	DFS(1,0);
	
	fout<<C.size()<<"\n";
	for(vector< vector<int> >::iterator big_it=C.begin();big_it!=C.end();++big_it)
	{
		sort(big_it->begin(),big_it->end());
		big_it->erase(unique(big_it->begin(),big_it->end()),big_it->end());
		for(vector<int>::iterator it=big_it->begin();it!=big_it->end();++it)
		{
			fout<<*it<<" ";
		}
		fout<<"\n";
	}
	fout.close();
	return 0;
}