Cod sursa(job #3248576)

Utilizator BeemoRobert Beemo Data 12 octombrie 2024 10:42:54
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.75 kb
#include <iostream>
#include <vector>
#include <fstream>

using namespace std;

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

int N , M ;
vector<bool>visited;
vector<vector<int>>adjList ;
void citire(int M) {
    for( int i = 1 ; i <= M ; i++ ) {
        int x , y;
       fin >> x >> y;
        adjList[x].push_back(y);
        adjList[y].push_back(x);}
}
void dfs(int node){
    visited[node]=true;
    for(auto x : adjList[node])
        if(!visited[x])
            dfs(x);

}

int main() {
   fin >> N >> M;
    adjList.resize(N+1);
    visited.resize(N+1);
    citire(M);
    int count = 0;
    for(int i = 1 ; i <= N ; i++)
        if(!visited[i]) {
            count++;
            dfs(i);
        }

            fout<<count<<endl;
            return 0;

}