Cod sursa(job #662225)

Utilizator Ifm-6Ilie Madalina Ifm-6 Data 16 ianuarie 2012 09:47:02
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include<stdio.h>
#define MAX 100010
using namespace std;
typedef struct nod { int info;
                     nod *next;} pnod;
pnod *G[MAX];
int viz[MAX];
int n,m;

void DFs(int nod1)
{
viz[nod1]=1; 
pnod *a; 
for (a=G[nod1];a!=NULL;a=a->next)
   if (viz[a->info]==0) DFs(a->info);
}

int main() 
{ pnod*a;
int i,x,y;
 
freopen("dfs.in", "r",stdin);
freopen("dfs.out", "w",stdout);
scanf("%d %d",&n,&m);
for (i=1;i<=m;i++)
 {
       scanf("%d %d",&x,&y);
       a=new nod;
       a->next=G[x];
       a->info=y;
       G[x]=a; 
       
       a=new nod;
       a->next=G[y];
       a->info=x;
       G[y]=a;
       }
int conex=0;            
for (i=1;i<=n;i++)
    if (viz[i]==0)  {
                    conex++; 
                    DFs(i);}
printf("%d\n",conex);
return 0;
}