Cod sursa(job #890544)

Utilizator BarracudaFMI-Alex Dobrin Barracuda Data 25 februarie 2013 10:20:43
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.38 kb
//Steaua -Chelsea 2 0
#include<fstream>
#include<vector>
#define nmax 200001
using namespace std;
 
int i,j,n,m,niv[nmax],c[nmax],viz[nmax],r1[nmax],r2[nmax],x,y,cr=0,nr=0;
vector<int> a[nmax];
vector<int> sol[nmax];
void add(int a,int b){
     
    int x,y;
    nr++;
    
    do{
    	
        x=r1[cr];
        y=r2[cr--];
        sol[nr].push_back(y);
    }while(x!=a||y!=b);
    sol[nr].push_back(x);
}

void dfs(int nod,int tata){
     
    int x,i;
    niv[nod]=niv[tata]+1;
    c[nod]=niv[nod];
    viz[nod]=1;
    for(i=0;i<a[nod].size();++i){
         
        x=a[nod][i];
        if(!viz[x]){
             
            r1[++cr]=nod;
            r2[cr]=x;
            dfs(x,nod);
            if(c[x]<c[nod])
                c[nod]=c[x];
            if(c[x]>=niv[nod])
                add(nod,x);
        }
        else
            if(x!=tata&&c[x]<c[nod])
                c[nod]=c[x];
    }
}
int main(){
     
    freopen("biconex.in","r",stdin);
    freopen("biconex.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++){
         
        scanf("%d%d",&x,&y);
        a[x].push_back(y);
        a[y].push_back(x);
    }
    dfs(1,0);
    printf("%d\n",nr);
    for(i=1;i<=nr;i++){
         
        for(j=0;j<sol[i].size();++j)
            printf("%d ",sol[i][j]);
        printf("\n");
    }
     
     
    return 0;
}