Cod sursa(job #279802)

Utilizator gabor_oliviu1991gaboru corupt gabor_oliviu1991 Data 12 martie 2009 23:31:06
Problema Parcurgere DFS - componente conexe Scor 5
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include<stdio.h>
#define N 100001

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

int main()
{
          freopen("dfs.in","r",stdin);
          freopen("dfs.out","w",stdout);
          
          int n, m, i, x, y, nr_comp = 0;
          
          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;
}