Cod sursa(job #3198784)

Utilizator Cyrex23Dumitrica Cezar Stefan Cyrex23 Data 30 ianuarie 2024 15:34:57
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.7 kb
#include <fstream>
#include <vector>
using namespace std;

ifstream cin("dfs.in");
ofstream cout("dfs.in");

const int N = 100005;

vector<vector<int>> graf;
vector<bool> viz;

struct nod{
    int n1, n2;
}e;

void dfs(int nod)
{
    viz[nod] = true;
    for (int i: graf[nod]){
        if(!viz[i])
            dfs(i);
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    graf.resize(N);
    viz.assign(N, false);
    for(int i = 0; i < m; i++){
        cin >> e.n1 >> e.n2;
        graf[e.n1].push_back(e.n2);
        graf[e.n2].push_back(e.n1);
    }
    int nr = 0;
    for(int i = 1; i <= n; i++){
        if(!viz[i]){
            nr++;
            dfs(i);
        }
    }
    cout << nr;
    return 0;
}