Cod sursa(job #3341531)

Utilizator andreiomd1Onut Andrei andreiomd1 Data 19 februarie 2026 20:40:43
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.77 kb
#include <fstream>
#include <vector>

using namespace std;
using Graph = vector<vector<int>>;

void dfs(const int node, const Graph &G, vector<bool> &used)
{
    used[node] = true;

    for (const int &adj : G[node])
        if (!used[adj])
            dfs(adj, G, used);

    return;
}

int main()
{
    ifstream f("dfs.in");
    ofstream g("dfs.out");

    int n = 0, m = 0;
    f >> n >> m;

    Graph G(n + 1);
    for (int e = 0; e < m; ++e)
    {
        int x = 0, y = 0;
        f >> x >> y;

        G[x].push_back(y), G[y].push_back(x);
    }

    vector<bool> used((n + 1), false);

    int answer = 0;

    for (int i = 1; i <= n; ++i)
        if (!used[i])
        {
            ++answer;
            dfs(i, G, used);
        }

    g << answer << '\n';

    return 0;
}