Cod sursa(job #843286)

Utilizator mariacMaria Constantin mariac Data 27 decembrie 2012 18:04:33
Problema Componente biconexe Scor 46
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 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 tata)
{	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,nod);
		    if(urca[nod]>urca[lv[nod][i]])urca[nod]=urca[lv[nod][i]];
			   else
				   if(urca[lv[nod][i]]>=niv)
				   {
						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(lv[nod][i]!=tata&&nivel[lv[nod][i]]<urca[nod]) 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);
	}
	for(i=1;i<=n;i++)
		if(!nivel[i])dfs(i,1,0);
	
	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";
	}
	   
}