Cod sursa(job #2930455)

Utilizator christalknightChristian Micea christalknight Data 28 octombrie 2022 15:07:29
Problema Parcurgere DFS - componente conexe Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.83 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

vector <int> matrix[100000];
long int n, m, nrCompConex;
bool vizitat[100000];

void citire(void);
void dfs(int poz);

int main(){
    fin>>n>>m;
    citire();
    for(int i = 1; i <= n; i++)
        if(!vizitat[i]){
            nrCompConex++;
            dfs(i);
            }
    fout<<nrCompConex;
    return 0;
}

void citire(void){
    int i, j;
    while(m--){
        fin>>i>>j;
        matrix[i].push_back(j);
        matrix[j].push_back(i);
        }
    }

void dfs(int poz){
    vizitat[poz] = true;
    for(int i = 0; i < matrix[poz].size(); i++){
        int vecin = matrix[poz][i];
        if(!vizitat[vecin]){
            dfs(vecin);
            }
        }
    }