Cod sursa(job #1377449)

Utilizator sherban26FMI Mateescu Serban-Corneliu sherban26 Data 5 martie 2015 21:49:42
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include <iostream>
#include <fstream>
#include <list>

#define NMAX 100010

using namespace std;

ifstream fin ("dfs.in");
ofstream fout ("dfs.out");

int n, m;
list<int> list_ad[NMAX];
int viz[NMAX];
int rez;

void dfs(int nod)
{
    viz[nod] = 1;

    for (list<int>::iterator it = list_ad[nod].begin(); it != list_ad[nod].end(); ++it)
    {
        if (viz[*it] == 0)
        {
            viz[*it] = 1;
            dfs(*it);
        }
    }
}

int main()
{
    fin >> n >> m;

    int first, second;
    for (int i = 0; i < m; ++i)
    {
        fin >> first >> second;
        list_ad[first].push_back(second);
        list_ad[second].push_back(first);
    }

    int j = 1;
    for (j = 1; j <= n; ++j)
    {
        if (viz[j] == 0)
        {
            dfs(j);
            ++rez;
        }
    }

    fout << rez;

    return 0;
}