Cod sursa(job #3225328)

Utilizator Cristian243Cristian-Stefan Lazar Cristian243 Data 17 aprilie 2024 13:11:16
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.27 kb
#include <bits/stdc++.h>
#include <iostream>
using namespace std;

class Solutuion {
 private:
    size_t N;
    size_t M;
    vector<vector<size_t>> adj;
    vector<bool> visited;

 public:
    explicit Solutuion(ifstream &in) {
        in >> N >> M;
        adj.resize(N + 1);
        visited.resize(N + 1, false);

        size_t node1, node2;
        for (size_t i = 1; i <= M; i++) {
            in >> node1 >> node2;

            adj[node1].push_back(node2);
            adj[node2].push_back(node1);
        }
    }

    void dfs(size_t node) {
        visited[node] = true;

        for (auto neighbour : adj[node]) {
            if (visited[neighbour])
                continue;
            
            dfs(neighbour);
        }
    }

    size_t solve() {
        bool done = false;
        size_t num_conex = 0;

        while (!done) {
            done = true;
            for (size_t node = 1; node <= N; node++)
                if (!visited[node]) {
                    dfs(node);
                    num_conex++;
                    done = false;
                }
        }
        
        return num_conex;
    }
};

int main() {
    ifstream in("dfs.in");
    ofstream out("dfs.out");
    
    out << Solutuion(in).solve();
    
    in.close();
    out.close();
    return 0;
}