Cod sursa(job #952412)

Utilizator alinaelenaFMI Colceag Alina alinaelena Data 23 mai 2013 13:51:01
Problema Componente biconexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
#include<cstdio>
#include<vector>
using namespace std;

 int n,m;
vector <int> vec[10001];
vector <int> q;
vector <int> sol[10001];

int viz[10001];
int tata2[10001];
int nivel[10001];
int nrcomp;

void read()
{
	int i,j,x,y;
	scanf("%d %d",&n,&m);
	for (i=1;i<=n;++i)
	{	scanf("%d %d",&x,&y);
	  vec[x].push_back(y);
	  vec[y].push_back(x);
	}
}



void dfs (int nod,int niv,int tata)
{
	q.push_back(nod);
	viz[nod]=niv;

	for (int i=0;i<vec[nod].size();++i)
    {
        int x=vec[nod][i];
	 if (viz[x]==0)
        {
            q.push_back(nod);
			tata2[x]=nod;
            dfs(x,niv+1,nod);

            if (viz[nod]>viz[x])
               viz[nod]=viz[x];
			
			        if (viz[x]<=niv)
		{
                    int m=q.size();
			m--;
                    
                    nrcomp++;

                    while (nod!=q[m])
					{
					sol[nrcomp].push_back(q[m]);
			      q.pop_back();
				  m--;
					}
			
	    } 
		else
			if (tata2[x]!=nod)
			{ viz[nod]=viz[x];
        
           }
        }
}

}


void write()
{
	int i,j;
printf("%d\n",nrcomp);
        for ( i=1;i<=nrcomp;i++)
	{
            for (j=0;j<sol[i].size();++j)
                printf("%d ",sol[i][j]);
			 printf("\n");
	            
}
         
}


int main()
{
	int i;
	freopen("biconexe.in","r",stdin);
	freopen("biconexe.out","w",stdout);
	read();
	for (i=1;i<=n;++i) 
		if (!nivel[i])
			dfs(i,1,0);
		
write();
}