Cod sursa(job #1582948)

Utilizator PraetorGrigorosoaia Florin Praetor Data 28 ianuarie 2016 17:18:15
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include<fstream>
#include<stdlib.h>
#define NRMAXNXQ 100001

using namespace std;

FILE*in;
ofstream out("dfs.out");

long nr_nxq; // numarul de noduri
long nr_muchii; // numarul de muchii
long *LA[NRMAXNXQ];
long visited[NRMAXNXQ];
long nr_componente_conexe;

void read()
{
    in=fopen("dfs.in", "r");

    fscanf(in, "%ld%ld", &nr_nxq, &nr_muchii);

    for (long i=1; i<=nr_nxq; i++)
    {
        LA[i]=(long *)realloc(LA[i], sizeof(long));
        LA[i][0]=0;
    }

    for (long i=1; i<=nr_muchii; i++)
    {
        long x, y;

        fscanf(in, "%ld%ld", &x, &y);

        LA[x][0]++;
        LA[x]=(long *)realloc(LA[x], (LA[x][0]+1)*sizeof(long));
        LA[x][LA[x][0]]=y;

        LA[y][0]++;
        LA[y]=(long *)realloc(LA[y], (LA[y][0]+1)*sizeof(long));
        LA[y][LA[y][0]]=x;
    }
}

void DFS(int nxq)
{
    visited[nxq]=nr_componente_conexe;

    for (long i=1; i<=LA[nxq][0]; i++)
        if (!visited[LA[nxq][i]])
            DFS(LA[nxq][i]);
}

void solve()
{
    for (long i=1; i<=nr_nxq; i++)
        if (!visited[i])
        {
            nr_componente_conexe++;
            DFS(i);
        }
}

void show()
{
    out<<nr_componente_conexe;
}

int main()
{
    read();
    solve();
    show();

    return 0;
}