Cod sursa(job #1650185)

Utilizator LolkekzorChiorean Tudor Lolkekzor Data 11 martie 2016 17:03:58
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.66 kb
#include <fstream>
#include <list>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");

int n, m, i, x, y, ans;
list<int> graf[100100];
bool vizitat[100100];

void DFS(int nod) {
    vizitat[nod] = true;
    for (list<int>::iterator it = graf[nod].begin() ; it != graf[nod].end() ; it++)
        if (!vizitat[*it])
            DFS(*it);
}

int main() {
    fin>>n>>m;
    for (i = 1 ; i <= m ; i++) {
        fin>>x>>y;
        graf[x].push_back(y);
        graf[y].push_back(x);
    }

    for (i = 1 ; i <= n ; i++) {
        if (!vizitat[i]) {
            DFS(i);
            ++ans;
        }
    }

    fout<<ans;
}