Cod sursa(job #2786178)

Utilizator qubitrubbitQubit Rubbit qubitrubbit Data 20 octombrie 2021 14:48:28
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.37 kb
#include <fstream>
#include <vector>
using namespace std;

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

class Graph
{
private:
    int cntNodes;
    vector<vector<int>> adjList;

    void dfs(int nodeId, bool visited[])
    {
        visited[nodeId] = true;
        for (int childId : adjList[nodeId])
        {
            if (!visited[childId])
            {
                dfs(childId, visited);
            }
        }
    }

public:
    Graph(int n)
    {
        cntNodes = n;
        for (int i = 0; i < n; ++i)
        {
            adjList.push_back(vector<int>());
        }
    }

    void addEdge(int from, int to, bool oriented)
    {
        adjList[from].push_back(to);
        if (!oriented)
        {
            adjList[to].push_back(from);
        }
    }

    int countConnComp()
    {
        bool visited[cntNodes];
        fill(visited, visited + cntNodes, false);
        int cnt = 0;
        for (int i = 0; i < cntNodes; ++i)
        {
            if (!visited[i])
            {
                ++cnt;
                dfs(i, visited);
            }
        }
        return cnt;
    }
};

int n, m, a, b;
int main()
{
    fin >> n >> m;
    Graph g(n);
    while (m-- > 0)
    {
        fin >> a >> b;
        g.addEdge(a - 1, b - 1, false);
    }
    fout << g.countConnComp();
    return 0;
}