Cod sursa(job #2219195)

Utilizator david420Bancsiko David david420 Data 7 iulie 2018 19:00:59
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

ifstream f("dfs.in");
ofstream g("dfs.out");

//const int NLIM = 100005;
int N, M;
bool latogatott[100005];

vector <int> elek[100005];

int komp;


void be() {
    f >> N >> M;

    for(int i = 1; i <= M; ++i) {
        int x, y;
        f >> x >> y;
        elek[x].push_back(y);
        elek[y].push_back(x);
    }
}

void DFS(int x) {
    latogatott[x] = true;

    for(unsigned int i = 0; i < elek[x].size(); ++i) {
        int Szomszed = elek[x][i];
        if(!latogatott[Szomszed])
            DFS(Szomszed);
    }
}

void Osszefugg() {
    for(int i = 1; i <= N; ++i) {
        if(!latogatott[i]) {
            komp++;
            //cout << komp << endl;
            DFS(i);
        }
    }
}

int main()
{
    be();
    Osszefugg();
    g << komp;
    return 0;
}