Cod sursa(job #316832)

Utilizator raica_cristiraica dumitru cristian raica_cristi Data 21 mai 2009 12:17:50
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include<stdio.h>
#define dim 100000
int n,i,k,m,x,y;
char viz[dim];
struct nod 
{
    int el;
    nod *next;
};
nod *liste[dim];
void add(nod *& prim, int y)
{
    nod *p = new nod ;
    p -> el=y;
    p -> next= prim;
    prim= p ;
  
}
void afis(nod * p)
{
     
    while(p)
    {
        printf("%d ",p -> el);
        p= p->next;
        
    }
}
void read()
{
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)
        scanf("%d%d",&x,&y),     add(liste[x],y),     add(liste[y],x);
}
int bf(int i)
{
  nod*p;
  viz[i]=1;
  for(p=liste[i] ; p ; p = p->next )
  if(!viz[p->el] )
  bf(p->el);

}
int main ()
{
    freopen("dfs.in","r",stdin);
    freopen("dfs.out","w",stdout);
    read();
    int val=0;
  //  for(i=1;i<=n;i++)
  //  afis(liste[i]), printf("\n");
    for(i=1;i<=n;i++)
    
     if(!viz[i])
     bf(i),
     val++;
    
    printf("%d\n",val);
    
  
    return 0;
}