Cod sursa(job #1146809)

Utilizator vladrochianVlad Rochian vladrochian Data 19 martie 2014 12:09:05
Problema Componente biconexe Scor 46
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include <fstream>
#include <list>
#define fori(l) for(list<int>::iterator it=(l).begin();it!=(l).end();++it)
using namespace std;
int n,m,bcni;
list<int> g[100001],*crt,*bcn[100001];
int level[100001],low[100001];
void dfs(int nod,int tt)
{
	level[nod]=low[nod]=level[tt]+1;
	fori(g[nod])
	{
		if(*it==tt)
			continue;
		if(!level[*it])
		{
			dfs(*it,nod);
			low[nod]=min(low[nod],low[*it]);
			if(!tt || low[*it]>=level[nod])
			{
				crt->push_back(nod);
				bcn[++bcni]=crt;
				crt=new list<int>;
			}
		}
		else
			low[nod]=min(low[nod],level[*it]);
	}
	crt->push_back(nod);
}
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int main()
{
	int i,j;
	fin>>n>>m;
	while(m--)
	{
		fin>>i>>j;
		g[i].push_back(j);
		g[j].push_back(i);
	}
	crt=new list<int>;
	for(i=1;i<=n;++i)
		if(!level[i])
		{
			crt->clear();
			dfs(i,0);
		}
	fout<<bcni<<"\n";
	for(i=1;i<=bcni;++i)
	{
		fori(*(bcn[i]))
			fout<<*it<<" ";
		fout<<"\n";
	}
	return 0;
}