Cod sursa(job #952413)

Utilizator alinaelenaFMI Colceag Alina alinaelena Data 23 mai 2013 13:53:48
Problema Componente biconexe Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.53 kb
#include<stdio.h>
#include<vector>
#define DIM 50005
  
using namespace std; 

struct muchie
{ int x,y;};
 muchie vec[DIM];
 
 int n,m,niv[DIM],comp[DIM],viz[DIM],nr;
vector<int> v[DIM],sol[DIM];
  
void read()
{
	int x,y;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i)
    {
        scanf("%d%d",&x,&y);
        v[x].push_back(y);
        v[y].push_back(x);
    }
}
  
int num;
  
void dfs(int nod,int tata)
{
	int xnou,ynou;
	
    niv[nod]=niv[tata]+1;
    comp[nod]=niv[nod];
    viz[nod]=1;
	
    for(int i=0;i<v[nod].size();++i)
    {
        int x=v[nod][i];
        if(!viz[x])
        {
            vec[++nr].x=nod;
            vec[nr].y=x;
            dfs(x,nod);
            if(comp[x]<comp[nod])
                comp[nod]=comp[x];
            if(comp[x]>=niv[nod])
			{
				   
    ++num;
    do
    { 
		
        xnou=vec[nr].x;
        ynou=vec[nr--].y;
        sol[num].push_back(ynou);
    }
    while(xnou!=nod||ynou!=x);
    sol[num].push_back(xnou);
			} 
		}
		
	else if(tata!=x&&comp[x]<comp[nod])
            comp[nod]=comp[x];
    }
}
  
int f[10000];
void write()
{
	
	/*for (int i=1;i<=n;++i)
		f[comp[i]]=1;
	for (int i=1;i<=10000;++i)
		if (f[i]) nr++;*/
	 printf("%d\n",num);
    for(int i=1;i<=num;++i)
    {
        for(int j=0;j<sol[i].size();++j)
            printf("%d ",sol[i][j]);
            printf("\n");
    }
}

int main()
{
	freopen("biconex.in","r",stdin);
	freopen("biconex.out","w",stdout);
    read();
	
    dfs(1,0);
	write();
}