Cod sursa(job #630640)

Utilizator ELHoriaHoria Cretescu ELHoria Data 6 noiembrie 2011 09:34:29
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.41 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>

using namespace std;
typedef pair<int,int> PII;
typedef vector<int> VI;

ifstream fin("biconex.in");
ofstream fout("biconex.out");

const int NMAX = 100002;
int N , M;
VI G[NMAX] , dfn , low;
vector< VI > C;
stack<PII> S;

void read_data()
{
	int x , y;
	for(fin>>N>>M;M;M--)
	{
		fin>>x>>y;
		G[x].push_back(y);
		G[y].push_back(x);
	}
	
	dfn.resize(N+1,-1);
	low.resize(N+1);

}

void cache_bc(const int x,const int y)
{
	vector<int> con; int tx , ty;
	do 
	{	tx = S.top().first , ty = S.top().second;
		S.pop(); con.push_back(tx) , con.push_back(ty); 
	}	while(x!=tx || y!=ty);
	C.push_back(con);
}
void dfs(const int nod,const int fn,int num)
{
	dfn[nod] = low[nod] = num;
	for(VI::const_iterator it=G[nod].begin();it!=G[nod].end();++it)
	if(fn!=*it)
	{
		if(dfn[*it]==-1)
		{
			S.push(make_pair(nod,*it));	
			dfs(*it,nod,num+1); 
			low[nod] = min(low[nod],low[*it]);
			if(low[*it]>=dfn[nod])	cache_bc(nod,*it);
		}
		else
		low[nod] = min(low[nod],dfn[*it]);
	}
}


void print()
{
	fout<<C.size()<<'\n';
	for(size_t i=0;i<C.size();++i)
	{
		sort(C[i].begin(),C[i].end());
		C[i].erase(unique(C[i].begin(),C[i].end()),C[i].end());
		for(size_t j=0;j<C[i].size();++j)
			fout<<C[i][j]<<' ';
		fout<<'\n';
	}
	
}

int main()
{
	read_data();
	dfs(1,0,0);
	print();
	return 0;
}