Cod sursa(job #782288)

Utilizator ion824Ion Ureche ion824 Data 26 august 2012 17:07:43
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.66 kb
#include<fstream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef struct lnod{
        int vf;
        struct lnod *next;
        }*Nod;
const int NM=100005;
int N,M,stx[NM+NM],sty[NM+NM],vf,nrC;
int dfn[NM],l[NM];
Nod a[NM],C[NM];
bool viz[NM];

void add(Nod &q,int x){
     Nod p=new lnod;
     p->vf=x;
     p->next=q;
     q=p;
     }

void comp(int x,int y){
     int dx,dy;
     ++nrC;
     do{
       dx=stx[vf]; dy=sty[vf--];
       add(C[nrC],dx); add(C[nrC],dy);
     }while(dx!=x || dy!=y);         
}

void dfs(int nod,int last,int num){
     dfn[nod]=l[nod]=num;
     for(Nod p=a[nod];p;p=p->next)
     {
       if(p->vf==last)continue;
       if(dfn[p->vf]==-1)
        {
         stx[++vf]=nod; sty[vf]=p->vf;
         dfs(p->vf,nod,num+1);
         l[nod]=min(l[nod],l[p->vf]);               
         if(l[p->vf] >= dfn[nod])
           comp(nod,p->vf);              
        }
       else l[nod]=min(l[nod],dfn[p->vf]);      
     }          
}

int main(void){
    ifstream fin("biconex.in");
    ofstream fout("biconex.out");
    int i,x0,y0;
    fin>>N>>M;
    for(i=1;i<=M;++i)
    {
     fin>>x0>>y0;
     add(a[x0],y0);
     add(a[y0],x0);                                   
    }
    
    memset(dfn,-1,sizeof(dfn)); 
    dfs(1,0,0);
   
    
    fout<<nrC<<'\n';
    for(i=1;i<=nrC;++i)
      {
       x0=0;       
       for(Nod p=C[i];p;p=p->next)
         dfn[++x0]=p->vf;  
       sort(dfn+1,dfn+x0+1);
       for(y0=1;y0<=x0;++y0)
         if(dfn[y0]!=dfn[y0-1])fout<<dfn[y0]<<' ';     
       fout<<'\n';                                         
      } 
 return 0;   
}