Cod sursa(job #3324919)

Utilizator tudor13mai@gmail.comBuciuman Tudor [email protected] Data 24 noiembrie 2025 09:18:15
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.86 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
vector<vector<int>> v(100100);
int w[100100];
int d[100100];
int n,m,s;
int num=0;
long long M;
void BFS(int a){
    queue<int> q;
    q.push(a);
    w[a]=1;
    d[a]=0;
    while(!q.empty()){
    int r=q.front();
        q.pop();
    for(auto e : v[r]){
        if(!w[e]){
        w[e]=1;
        d[e]=d[r]+1;
        q.push(e);
        }
    }
    //w[r]=1;
    }

}
void DFS(int a){
    w[a]=1;
    for(auto e : v[a]){
        if(!w[e]){
        DFS(e);
        }
    }
}
int main(){
    int a,b;
    fin>>n>>M;
    for(long long i=1; i<=M; i++){
        fin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    for(int i=1; i<=n; i++){
    if(!w[i])
    DFS(i),num++;
    }
    fout<<num<<" ";
    return 0;
}