Cod sursa(job #2858391)

Utilizator DajaMihaiDaja Mihai DajaMihai Data 27 februarie 2022 14:24:22
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.86 kb
#include <stdio.h>
#include <vector>
#define N 100000

using namespace std;

vector <int> g[N + 1];
int comp[N + 1];
int n;

void dfs(int node) {
    for (const int& vecin : g[node]) {
        if ( comp[vecin] == 0) {
            comp[vecin] = comp[node];
            dfs(vecin);
        }
    }
}

inline void addMuchie(int a, int b) {
    g[a].push_back(b);
    g[b].push_back(a);
}

FILE *in, *out;
in = fopen("dfs.in", "r");
out = fopen("dfs.out", "w");

int main() {
    int m, a, b;

    fscanf( in, "%d%d", &n, &m);
    for (int i = 0; i < m; i ++) {
        fscanf(in, "%d%d", &a, &b);
        addMuchie(a, b);
    }

    int nr = 0;
    for (int i = 1; i <= n; i ++) {
        if (comp[i] == 0) {
            nr ++;
            comp[i] = nr;
            dfs(i);
        }
    }


    fprintf(out, "%d\n", nr);
    return 0;
}