Cod sursa(job #296288)

Utilizator sigridMaria Stanciu sigrid Data 4 aprilie 2009 16:03:45
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include<stdio.h>
#include<stdlib.h>

#define dim 200002

int *a[dim];
int viz[dim];

int N, M, comp;

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

int main()
{
    int i, x, y;
    
    freopen("dfs.in", "r", stdin);
    freopen("dfs.out", "w", stdout);
    
    scanf("%d %d", &N, &M);
    
    for(i = 1; i <= N; i++)
    {
          a[i] = (int *)realloc(a[i], sizeof(int));
          
          a[i][0] = 0;
    }

    int xx;

    while( M )
    {
	   scanf("%d %d", &x, &y);

	   xx=x;
           
           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]] = xx;
           
           M--;
    }

    for(i = 1; i <= N; i++)
          if(! viz[i])
          {
               comp++;
               
               dfs(i);
          }
    
    printf("%d \n", comp);
               
    return 0;
}