Cod sursa(job #2400583)

Utilizator eduardandrei20Nechifor Eduard Andrei eduardandrei20 Data 8 aprilie 2019 21:19:36
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.87 kb
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

const int dim = 100001;
vector<int>graph[dim];
const int infinity = 10000000;
int components, nodes, edges;
bool check[dim];

void input() {
    in >> nodes >> edges;
    for (int i = 1; i <= edges; i++) {
        int u, v;
        in >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
}

void dfs(int node) {
    check[node] = true;
    for (size_t j = 0; j < graph[node].size(); j++) {
        int vecin = graph[node][j];
        if (!check[vecin]) {
            dfs(vecin);
        }
    }
}

int main() {

    input();
    for (int i = 1; i <= nodes; i++) {
        if (!check[i]) {
            components++;
            dfs(i);
        }
    }
    out << components;

	return 0;
}