Cod sursa(job #205981)

Utilizator mika17Mihai Alex Ionescu mika17 Data 3 septembrie 2008 20:34:05
Problema Parcurgere DFS - componente conexe Scor 5
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include <stdio.h>
#include <stdlib.h>

int N,M;
int * A[100000];

void citire()
{
    freopen("dfs.in","r",stdin);
    scanf("%d %d",&N,&M);

    for(int i = 0 ; i < N; ++i)
    {
       A[i] = (int*) malloc(sizeof(int));
       A[i][0] = 0;
    }

    for(int i = 0 ; i < M; ++i)
    {
     int u,v;
     scanf("%d %d",&u,&v);
     A[u][0] ++;
     A[u] = (int*) realloc(A[u], (A[u][0] + 1) * sizeof(int));
     A[u][A[u][0]] = v;
    }
}

bool vis[100000];
int nc;

void dfs(int i)
{
 vis[i] = 1;
 for(int j = 1; j <= A[i][0]; ++j)
    dfs(A[i][j]);
}

void conex()
{
 for(int i = 0 ; i < N; ++i)
    if(!vis[i])
      nc ++, dfs(i);

 freopen("dfs.out","w",stdout);
 printf("%d",nc);
}

int main()
{
 citire();
 conex();
 return 0;
}