Cod sursa(job #2783457)

Utilizator icnsrNicula Ionut icnsr Data 14 octombrie 2021 15:02:24
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.78 kb
#include <vector>
#include <cstdio>

class Graph
{
public:
        Graph(std::size_t nr_noduri, std::vector<std::vector<int>>&& l_adiacenta)
            : nr_noduri(nr_noduri)
            , l_adiacenta(std::move(l_adiacenta))
        {
        }

        int componente_conexe() const
        {
                std::vector<bool> visited(nr_noduri + 1, false);

                int res = 0;
                for(int node = 1; node <= (int)nr_noduri; ++node)
                {
                        if(!visited[node])
                        {
                                ++res;
                                DFS(visited, node);
                        }
                }

                return res;
        }

private:
        void DFS(std::vector<bool>& visited, int start) const
        {
                visited[start] = true;

                for(int v : l_adiacenta[start])
                {
                        if(!visited[v])
                        {
                                DFS(visited, v);
                        }
                }
        }

private:
        std::size_t nr_noduri;
        std::vector<std::vector<int>> l_adiacenta;
};

int main()
{
        std::freopen("dfs.in", "r", stdin);
        std::freopen("dfs.out", "w", stdout);

        const Graph g = []()
        {
                int n, m;
                std::scanf("%d %d", &n, &m);

                std::vector<std::vector<int>> list(n + 1);
                for(int i = 0; i < m; ++i)
                {
                        int x, y;
                        std::scanf("%d %d", &x, &y);

                        list[x].push_back(y);
                        list[y].push_back(x);
                }

                return Graph(n, std::move(list));
        }();

        std::printf("%d\n", g.componente_conexe());
}