Cod sursa(job #3313137)

Utilizator domdiridomdidomDominik domdiridomdidom Data 2 octombrie 2025 12:39:28
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.34 kb
#include <fstream>
#include <vector>
#include <queue>

struct Node{
    std::vector<int> edges;
    int utHossz;
    Node(){
        utHossz = -1;
    }
    void addEdge(int x){
        edges.push_back(x); 
    }
    int nrEdges(){
        return edges.size();
    }
};

int main(){
    std::ifstream bem("dfs.in");
    std::ofstream kim("dfs.out");
    int n, m;
    bem >> n >> m;
    std::vector<Node> nodes(n);
    for(int i = 0; i < m; i++){
        int x, y;
        bem >> x >> y;
        x--;
        y--;
        nodes[x].addEdge(y);
        nodes[y].addEdge(x);
    }

    int nr = 0;

    for(int i = 0; i < n; i++){
        if(nodes[i].utHossz == -1){
            std::queue<Node> varoLista;
            nodes[i].utHossz = 0;
            varoLista.push(nodes[i]);
            while(!varoLista.empty()){
                Node jelenlegi = varoLista.front();
                varoLista.pop();
                for(int j = 0; j < jelenlegi.nrEdges(); j++){
                    if(nodes[jelenlegi.edges[j]].utHossz == -1){
                        nodes[jelenlegi.edges[j]].utHossz = jelenlegi.utHossz + 1;
                        varoLista.push(nodes[jelenlegi.edges[j]]);
                    }
                }
            }
            nr++;
        }
    }
    kim << nr;
    bem.close();
    kim.close();
}