Cod sursa(job #843328)

Utilizator mariacMaria Constantin mariac Data 27 decembrie 2012 20:04:27
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.54 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];
bool viz[100005];
int nr;

int n,m;
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);
	int siz;
	siz=lv[nod].size();
	for(i=0;i<siz;i++)
	{
		int x=lv[nod][i];
		if(!nivel[x])
		{ 	
			
			stack.push_back(nod);
			dfs(x,niv+1,nod);
		    if(urca[nod]>urca[x])urca[nod]=urca[x];
			   else
				   if(urca[x]>=niv)
				   {
						int u,j;
						u=stack.size()-1;
						
						nr++;
						
						while(stack[u]!=nod)
						{ 
							if(!viz[stack[u]])
							   { 
								   com[nr].push_back(stack[u]);	
							       viz[stack[u]]=1;
								}
							u--;
							stack.pop_back();
							
						}
						if(!viz[stack[u]])com[nr].push_back(stack[u]);
						stack.pop_back();
						
						u=com[nr].size();
						for(j=0;j<u;j++)
							viz[com[nr][j]]=0;
				
						       
				   }
        }
		else
			if(x!=tata&&nivel[x]<urca[nod]) urca[nod]=nivel[x];
    } 
}


		  



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";
	}
	   
}