Cod sursa(job #285309)

Utilizator AndreiDDiaconeasa Andrei AndreiD Data 22 martie 2009 15:06:33
Problema Parcurgere DFS - componente conexe Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 0.96 kb
#include <stdio.h>
#include <stdlib.h>

int *a[100001];
int n,m,x,y,viz[100001],nr=0;

void dfs(int nod)
{
    int i;
    viz[nod]=1;
    for (i=1;i<=a[nod][0];++i)
          if (!viz[a[nod][i]])
               dfs(a[nod][i]);
}              

int main()
{
    int i;
    freopen("dfs.in","r",stdin);
    freopen("dfs.out","w",stdout);
    
    scanf("%d %d\n", &n,&m);   
    for (i=1;i<=n;++i)
    {
        a[i]=(int *)realloc(a[i], sizeof(int));
        a[i][0]=0;
    }
    while(m--)
    {
        scanf("%d %d\n", &x,&y);
        a[x][0]++;
        a[x]=(int *)realloc(a[x], (a[x][0]+1)*sizeof(int));
        a[x][a[x][0]]=y;
        a[y][0]++;
        a[y]=(int *)realloc(a[y], (a[y][0]+1)*sizeof(int));
        a[y][a[y][0]]=x;
    }
    
    for (i=1;i<=n;++i)
          if (!viz[i])
               {
                    nr++;
                    dfs(i);
                }
    printf("%d", nr);
    return 0;
}