Cod sursa(job #1147002)

Utilizator vladrochianVlad Rochian vladrochian Data 19 martie 2014 15:00:48
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include <fstream>
#include <list>
#include <stack>
#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],bcn[100001];
stack<int> st;
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])
		{
			st.push(*it);
			dfs(*it,nod);
			low[nod]=min(low[nod],low[*it]);
			if(!tt || low[*it]>=level[nod])
			{
				++bcni;
				bcn[bcni].push_back(st.top());
				while(st.top()!=*it)
				{
					st.pop();
					bcn[bcni].push_back(st.top());
				}
				st.pop();
				bcn[bcni].push_back(nod);
			}
		}
		else
			low[nod]=min(low[nod],level[*it]);
	}
}
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);
	}
	for(i=1;i<=n;++i)
		if(!level[i])
			dfs(i,0);
	fout<<bcni<<"\n";
	for(i=1;i<=bcni;++i)
	{
		fori(bcn[i])
			fout<<*it<<" ";
		fout<<"\n";
	}
	return 0;
}