Cod sursa(job #2580256)

Utilizator TveinDenisDenis Tvein TveinDenis Data 13 martie 2020 14:25:16
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.26 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>

using std::cout;
using std::endl;
using std::cin;
using std::vector;
using std::queue;
using std::stack;
using std::fstream;
using std::ios;
using std::sort;

fstream file1("dfs.in", ios::in);
fstream file2("dfs.out", ios::out);

int nr_noduri, nr_muchii;
vector<int> vecini[100005];
vector<bool> vizitat(100005);

int nr_comp_conex();
void form_vecini();
void dfs(int start);

int main(int argc, char** argv) {

    file1 >> nr_noduri >> nr_muchii;
    form_vecini();

    file2 << nr_comp_conex();

    file1.close();
    file2.close();
    return 0;
}

int nr_comp_conex() {
    int count{ 0 };
    for (int i{ 1 }; i <= nr_noduri; i++) {
        if (!vizitat[i]) {
            dfs(i);
            count++;
        }
    }
    return count;
}

void dfs(int start) {
    vizitat[start] = true;
    for (auto it = vecini[start].begin(); it != vecini[start].end(); it++) {
        if (!vizitat[*it]) {
            vizitat[*it] = true;
            dfs(*it);
        }
    }
}

void form_vecini() {
    int i, j;
    while (file1 >> i >> j) {
        vecini[i].push_back(j);
        vecini[j].push_back(i);
    }
}