Cod sursa(job #3238387)

Utilizator Tudor567Voica Tudor Tudor567 Data 24 iulie 2024 21:43:21
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.76 kb
#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
int n,ii,jj,k = 0;
long m;
    ifstream in("dfs.in");
    ofstream out("dfs.out");

void dfs(vector<int>a[],int t,bool ver[]){
    if(a[t].size()>0)
    for(int i = 0; i <= a[t].size()-1; i++)
        if(ver[a[t][i]] == 0){
        ver[a[t][i]] = 1;
        dfs(a,a[t][i],ver);
        }


}

int main(){
    in>>n>>m;
    bool ver[n+1]; vector<int>a[n+1];
    for(int i = 1; i <= n; i++)ver[i] = 0;
    for(int i = 1; i <= m; i++){
        in>>ii>>jj;
        a[ii].push_back(jj);
        a[jj].push_back(ii);
    }

    for(int i = 1; i <=n ; i++){
        if(ver[i] == 0){
        k++;
        ver[i] = 1;
        dfs(a,i,ver);
        }
    }
    out<<k;
}