Cod sursa(job #212588)

Utilizator socheoSorodoc Ionut socheo Data 5 octombrie 2008 21:05:11
Problema Parcurgere DFS - componente conexe Scor 85
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include<stdio.h>
int li[3][100000],nr,fin,parc,st,i,f[100000],j,n,m,ver[100000],coada[100000];
void bf(int nod)
{ st=1;
 fin=2;
 coada[st]=nod;
 f[nod]=nr;
 while(st<=fin)
 {   parc=ver[coada[st]];
   while(parc!=0)
     { if(f[li[1][parc]]==0)
        { coada[fin]=li[1][parc];
          f[li[1][parc]]=nr;
          fin++;           }
          parc=li[2][parc];
       }
    st++;
 }
}
int main()
{freopen("dfs.in","r",stdin);
 freopen("dfs.out","w",stdout);
 int k=1;
 scanf("%d%d",&n,&m);
 scanf("%d%d",&i,&j);
 while(i!=0&&j!=0)
  { li[1][k]=j;
    li[2][k]=ver[i];
    ver[i]=k;
    k++;
    li[1][k]=i;
    li[2][k]=ver[j];
    ver[j]=k;
    k++;
    i=0; j=0;
   scanf("%d%d",&i,&j);
  }

 for(i=1;i<=n;i++)
  { if(f[i]==0)
     { nr++;
     bf(i); }
 }
 printf("%d",nr);
return 0;
}