Cod sursa(job #3335785)

Utilizator meowwwMihai Filip meowww Data 23 ianuarie 2026 16:24:47
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.96 kb
#include <bits/stdc++.h>

using data = unsigned int;

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

void dfsProcedure(data node, std::vector<std::vector<data>>& graph, std::vector<char>& hasBeenVisited)
{
    hasBeenVisited[node] = true;
    for (data neighbour : graph[node])
        if (!hasBeenVisited[neighbour])
            dfsProcedure(neighbour, graph, hasBeenVisited);
}

int main()
{
    data nodeNum, edgeNum, x, y, connectedComps;

    fin >> nodeNum >> edgeNum;
    std::vector<std::vector<data>> graph(nodeNum + 1);
    std::vector<char> hasBeenVisited(nodeNum + 1, false);

    while (fin >> x >> y)
    {
        graph[x].push_back(y);
        graph[y].push_back(x);
    }

    for (size_t node = 1 ; node < hasBeenVisited.size(); ++node)
        if (!hasBeenVisited[node])
        {
            dfsProcedure(node, graph, hasBeenVisited);
            connectedComps += 1;
        }
    
    fout<<connectedComps;
                   
    return 0;
}