Cod sursa(job #793491)

Utilizator romircea2010FMI Trifan Mircea Mihai romircea2010 Data 3 octombrie 2012 01:34:48
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include <iostream>
#include <fstream>
#include <cstdlib>

using namespace std;

int N, M, *a[100010], nrc;
bool viz[100010];

inline void Read()
{
    ifstream f ("dfs.in");
    f>>N>>M;
    int i;
    for (i=1; i<=N; i++)
    {
        a[i] = (int *)realloc(a[i], sizeof(int));
        a[i][0] = 0;
    }
    int x, y;
    for (i = 1; i<=M; i++)
    {
        f>>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]] = y;
    }
    f.close();
}

inline void DFS(int x)
{
    viz[x] = true;
    for (int i = 1; i<=a[x][0]; i++)
        if (!viz[a[x][i]])
            DFS(a[x][i]);
}

inline void Write()
{
    ofstream g("dfs.out");
    g<<nrc<<"\n";
    g.close();
}

int main()
{
    Read();
    for (int i = 1; i<=N; i++)
        if (!viz[i])
        {
            nrc++;
            DFS(i);
        }
    Write();
    return 0;
}