Cod sursa(job #2662797)

Utilizator Silviu.Stancioiu@gmail.comSilviu Stancioiu [email protected] Data 24 octombrie 2020 15:12:16
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.88 kb
#include <fstream>
#include <vector>

using namespace std;

vector<vector<int>> graph;
vector<bool> visited;

void dfs(const int node)
{
    if (visited[node])
        return;

    visited[node] = true;

    for (auto neighbor : graph[node])
        dfs(neighbor);
}

int main()
{
    auto result = 0;

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

    int n, m;
    fin >> n >> m;

    graph.resize(n);
    visited = vector<bool>(n, false);

    for (auto i = 0; i < m; i++)
    {
        int x, y;
        fin >> x >> y;
        x--;
        y--;
        graph[x].push_back(y);
        graph[y].push_back(x);
    }

    fin.close();

    for (auto i = 0; i < n; i++)
    {
        if (!visited[i])
        {
            dfs(i);
            result++;
        }
    }

    fout << result;

    fout.close();

    return 0;
}