Cod sursa(job #2858295)

Utilizator ecaterinaEcaterina Stefanescu ecaterina Data 27 februarie 2022 12:46:27
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.91 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=1; i<=n; i++) {
        if (vizita[i] == 0) {
            dfs(i);
            nr++;
        }
    }

    fprintf(fout, "%d\n", nr);

    fclose(fin);
    fclose(fout);
    return 0;
}