Cod sursa(job #2589271)

Utilizator MiclosMiclos Eduard Miclos Data 25 martie 2020 23:36:19
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.9 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

ifstream fin("C:\\Users\\Eduard\\Documents\\CLionProjects\\dfs\\dfs.in");
ofstream fout("C:\\Users\\Eduard\\Documents\\CLionProjects\\dfs\\dfs.out");

const int N_MAX {100000};
int N, M, answer;

vector <int> Edges[N_MAX];
bool Check[N_MAX];

void DFS(int Node){

        Check[Node] = true;

        for(unsigned int i = 0; i<Edges[Node].size(); i++){
            int Next = Edges[Node][i];

            if(!Check[Next]){
              DFS(Next);
            };
        };

};

void Read(){

    fin >> N >> M;
    for(int i = 1; i<=M; i++){
        int x, y;
        fin >> x >> y;
        Edges[x].push_back(y);
        Edges[y].push_back(x);
    };

    for(int i = 1; i<=N; i++){
        if(!Check[i]){
            answer++;
            DFS(i);
        }
    };
    fout << answer << "\n";
};



int main(){
    Read();
return 0;

};