Cod sursa(job #843269)

Utilizator mariacMaria Constantin mariac Data 27 decembrie 2012 17:39:00
Problema Componente biconexe Scor 18
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include<fstream>
#include<vector>

using namespace std;


ifstream fin("biconex.in");
ofstream fout("biconex.out");
int urca[100001],nivel[100001];
vector <int> lv[100005];
vector <int> com[100005];
int nr;
vector <int> stack;
int cate,start;
void dfs(int nod,int niv)
{	int i;
	urca[nod]=niv;
	nivel[nod]=niv;
	stack.push_back(nod);
	for(i=0;i<lv[nod].size();i++)
	{
		if(!nivel[lv[nod][i]])
		{
			dfs(lv[nod][i],niv+1);
		    if(urca[nod]>urca[lv[nod][i]])urca[nod]=urca[lv[nod][i]];
			   else
				   if((urca[nod]==urca[lv[nod][i]]&&urca[nod]==niv)||urca[nod]<urca[lv[nod][i]])
				   {
						int u;
				       
						u=stack.size()-1;
					nr++;
					while(stack[u]!=nod)
					{	
						com[nr].push_back(stack[u--]);
						stack.pop_back();
					}
					com[nr].push_back(stack[u]);
				
						       
				   }
        }
		else
			if(nivel[lv[nod][i]]&&nivel[lv[nod][i]]<niv-1) urca[nod]=nivel[lv[nod][i]];
    }
}


		  


int n,m;

int main()
{
	int i;
	
	fin>>n;
	fin>>m;
	
	for(i=1;i<=m;i++)
	{	
		int x,y;
		fin>>x>>y;
		lv[x].push_back(y);
		lv[y].push_back(x);
	}
	stack.push_back(1);
	dfs(1,1);
	
	fout<<nr<<"\n";
	for(i=1;i<=nr;i++)
	{
		int j,k;
		k=com[i].size();
		for(j=0;j<k;j++)
			fout<<com[i][j]<<" ";
		fout<<"\n";
	}
	   
}