Cod sursa(job #2033145)

Utilizator damian_belesDamian Beles damian_beles Data 6 octombrie 2017 10:23:30
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include <fstream>
#include <vector>
#include <bitset>

using namespace std;

const int NMAX = 100005;

int N, M, counter;

vector<int> nodes[NMAX];
bitset<NMAX> visited;

void read() {
    ifstream fin ("dfs.in");
    fin >> N >> M;
    while (M--) {
        int x, y;
        fin >> x >> y;
        nodes[x].push_back(y);
        nodes[y].push_back(x);
    }
    fin.close();
}

void DFS(int node) {
    visited.set(node);
    for (const auto& it : nodes[node]) {
        if (!visited[it])
            DFS(it);
    }
}

void solve() {
    for (int i = 1; i <= N; ++i) {
        if (!visited[i]) {
            counter++;
            DFS(i);
        }
    }
    ofstream fout ("dfs.out");
    fout << counter;
    fout.close();
}

int main() {
    read();
    solve();
    return 0;
}