Cod sursa(job #1377446)

Utilizator sherban26FMI Mateescu Serban-Corneliu sherban26 Data 5 martie 2015 21:48:45
Problema Parcurgere DFS - componente conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 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;

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

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

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)
        {
            if (dfs(j))
                ++rez;
        }
    }

    fout << rez;

    return 0;
}