Cod sursa(job #279837)

Utilizator gabor_oliviu1991gaboru corupt gabor_oliviu1991 Data 13 martie 2009 00:05:19
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include<stdio.h>
#define N 100005

struct nod{int info;
           nod *urm;} *lista[N];
           
int viz[N];
           
void dfs(int vf)
{
             nod *p;
             viz[vf] = 1;
             for(p = lista[vf]; p; p = p->urm)
                   if(!viz[p->info])
                        dfs(p->info);
}

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