Cod sursa(job #2739823)

Utilizator RobertAcAcatrinei Robert-Marian RobertAc Data 10 aprilie 2021 11:18:10
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.67 kb
#include <bits/stdc++.h>

using namespace std;
ifstream in("dfs.in");
ofstream out("dfs.out");
vector<vector<int>> g(100001);
vector<bool> v(100001);
stack<int> s;
void dfs(){
    while(!s.empty()){
        int i=s.top();
        s.pop();
        v[i]=1;
        for(auto j:g[i]){
            if(!v[j])s.push(j);
        }
    }
}

int main(){
    int n,m;
    in>>n>>m;

    for(int i=0;i<m;i++){
        int x,y;
        in>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    int  rez=0;
    for(int i=1;i<=n;i++){
        if(!v[i]){
            s.push(i);
            dfs();
            rez++;
        }
    }
    out<<rez;
}