Cod sursa(job #2858104)

Utilizator ecaterinaEcaterina Stefanescu ecaterina Data 26 februarie 2022 23:44:40
Problema Parcurgere DFS - componente conexe Scor 35
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.89 kb
#include <stdio.h>
#include <vector>
using namespace std;

#define MAXN 100001

vector<int> graf[MAXN];
int vizita[MAXN];

void adauga(int a, int b) {
    graf[a].push_back(b);
    graf[b].push_back(a);
}

void dfs(int ind) {
    int vecin;
    
    vizita[ind] = 1;
    
    for(vecin=0; vecin<(int)graf[ind].size(); vecin++){
        if(vizita[graf[ind][vecin]]==0) {
            dfs(graf[ind][vecin]);
        }
    }
}

int main() {
    FILE *fin, *fout;
    fin = fopen("dfs.in", "r");
    fout = fopen("dfs.out", "w");
    
    int n, m, i, a, b, nr;
    
    fscanf(fin, "%d%d", &n, &m);
    
    for (i=0; i<m; i++) {
        fscanf(fin, "%d%d", &a, &b);
        adauga(a, b);
    }
    
    nr=0;
    for (i=0; i<n; i++) {
        if (vizita[i] == 0) {
            dfs(i);
            nr++;
        }
    }
    
    fprintf(fout, "%d\n", nr);
    
    fclose(fin);
    fclose(fout);
    return 0;
}