Cod sursa(job #739270)

Utilizator paunmatei7FMI Paun Matei paunmatei7 Data 22 aprilie 2012 16:20:23
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include<cstdio>
#include<stdlib.h>
#define nmax 100003
using namespace std;
int *A[nmax],v[nmax],i, j, n, m, x ,y ;
void parcurge(int k)
{
    int i;
    v[k] = 1;
    for(i = 1; i <= A[k][0] ;i++)
        if(v[A[k][i]] == 0 )
            parcurge(A[k][i]);
}
int main()
{
	freopen("dfs.in","r",stdin);
	freopen("dfs.out","w",stdout);
	int Nr = 0;
    scanf("%ld %ld",&n,&m); 
    for(i = 1; i <= n ;i++)
    {
        A[i] = (int *) realloc(A[i], sizeof(int));
        A[i][0] = 0;
    }
    for(i = 1; i<=m ;i++)
    {
		scanf("%ld %ld",&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(v[i]==0)
        {
            Nr++;
           parcurge(i);
        }
    printf("%ld",Nr);
    return 0;
}