Cod sursa(job #3222457)

Utilizator andrei_laurentiuRadu Andrei-Laurentiu andrei_laurentiu Data 10 aprilie 2024 11:06:03
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.97 kb
//
// Created by Laur on 4/10/2024.
//
#include <fstream>
#include <vector>
#include <iostream>

#define nmax 100005
using namespace std;

int n, m;
vector<int> graf[nmax];
vector<int> comp;

void dfs(int start, int nr) {
    comp[start] = nr;
    for(int x : graf[start]) {
        if(!comp[x]) {
            dfs(x, nr);
        }
    }
}
int main(){
//    ifstream fin("E:\\UPB_ACS_CTI\\anul_2\\sem_2\\PA\\all_problems\\lab_7\\dfs\\dfs.in");
//    ofstream fout("E:\\UPB_ACS_CTI\\anul_2\\sem_2\\PA\\all_problems\\lab_7\\dfs\\dfs.out");
    ifstream fin("date.in");
    ofstream fout("date.out");
    fin >> n;
    comp.assign(n+ 1, 0);
    fin >> m;
    int u, v;
    for(int i = 0; i < m; ++i) {
        fin >> u >> v;
        graf[u].push_back(v);
        graf[v].push_back(u);
    }
    int nr;
    for(int i = 1; i <= n; ++i) {
        if (!comp[i]) {
            ++nr;
            dfs(i, nr);
        }

    }

    fout << nr;

    return 0;
}