Cod sursa(job #1022433)

Utilizator Victor10Oltean Victor Victor10 Data 5 noiembrie 2013 13:47:11
Problema Parcurgere DFS - componente conexe Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include <iostream>
#include <fstream>
#define DM 10005
using namespace std;

int n, m, adiac [DM] [DM];
bool fost [DM];

void dfs (int nod)
{
    fost [nod] = 1;
    int i;
    for (i = 1; i <= n; ++ i)
    {
        if (adiac [nod] [i] && ! fost [i]) dfs (i);
    }
}



int main()
{
    int i, n1, n2, answ = 0;
    ifstream f("dfs.in");
    ofstream g("dfs.out");

    f >> n >> m;

    for (i = 1; i <= m; ++ i)
    {
        f >> n1 >> n2;
        adiac [n1] [n2] = adiac [n2] [n1] = 1;
    }

    for (i = 1; i <= n; ++ i)
    {
        if (! fost [i])
        {
            ++ answ;
            dfs (i);
        }
    }

    g << answ;


}