Cod sursa(job #736110)

Utilizator Theorytheo .c Theory Data 17 aprilie 2012 21:09:02
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include<fstream>
#include<stdlib.h>
#define nmax 100003
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
int *A[nmax];
int v[nmax];
int 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]);
}
void read()
{
    int Nr = 0;
    fin >> 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++)
    {
        fin >>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++)
//    {
//        for(j = 1; j <= A[i][0] ; j++)
//        {
//            fout<< A[i][j] <<" " ;
//
//        }
//        fout << '\n' ;
//    }
    for(i = 1; i <= n ;i++)
    {
        if(v[i]==0)
        {
            Nr++;
           parcurge(i);
        }

    }

    fout << Nr ;
}
int main()
{
    read();
    fin.close();
    fout.close();
    return 0;

}