Cod sursa(job #3318448)

Utilizator LiviuMmMarinica Liviu LiviuMm Data 28 octombrie 2025 12:40:50
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.7 kb
#include <iostream>
#include <fstream>
using namespace std;

int N, M, comp = 0;
int viz[100001], lst[100001][101], grad[100001];

void dfs(int nod) {
    viz[nod] = 1;
    for (int i = 0; i < grad[nod]; i++) {
        int vecin = lst[nod][i];
        if (!viz[vecin])
            dfs(vecin);
    }
}

int main() {
    ifstream f("dfs.in");
    ofstream g("dfs.out");

    f >> N >> M;
    for (int i = 1; i <= M; i++) {
        int x, y;
        f >> x >> y;
        lst[x][grad[x]++] = y;
        lst[y][grad[y]++] = x;
    }
    for (int i = 1; i <= N; i++) {
        if (!viz[i]) {
            comp++;
            dfs(i);
        }
    }

    g << comp << endl;

    return 0;
}