Cod sursa(job #2663628)

Utilizator rusuandrei32Rusu Andrei-Cristian rusuandrei32 Data 26 octombrie 2020 22:05:07
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.22 kb
#include <fstream>
#include <iostream>
#include <list>
#include <vector>

using namespace std;

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

class Graph {
    int vertices;
    list <int> *adj;

public:
    Graph(int v) : vertices(v) {
        adj = new list <int>[v];
    }

    void addEdge(int from, int to) {
        adj[from].push_back(to);
    }

    void dfs(int i, vector <bool> &visited) {
        visited[i] = true;

        for (auto &adjVal : adj[i])
            if (!visited[adjVal])
                dfs(adjVal, visited);
    }

    int countConnectedComponents() {
        int ans = 0;
        vector <bool> visited(vertices);

        for (int i = 1; i < vertices; ++i) {
            if (!visited[i]) {
                dfs(i, visited);

                ++ans;
            }
        }

        return ans;
    }

};


int main() {

    int N, M;
    in >> N >> M;
    
    Graph *myGraph = new Graph(N + 1);

    while (M--) {
        int from, to;
        in >> from >> to;

        myGraph -> addEdge(from, to);
        myGraph -> addEdge(to, from);
    }

    out << myGraph -> countConnectedComponents();

    in.close();
    out.close();

    return 0;
}