Cod sursa(job #3362871)

Utilizator horia.boeriuBoeriu Horia Andrei horia.boeriu Data 12 august 2026 20:40:45
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.89 kb
#include <iostream>

using namespace std;
const int MAXN = 100000;
int sef[MAXN + 1], siz[MAXN + 1];
int nrc;

int findsef(int i) {
    if (i == sef[i]) {
        return i;
    }
    return sef[i] = findsef(sef[i]);
}
void unesc(int x, int y) {
    x = findsef(x);
    y = findsef(y);
    if (x != y) {
        nrc--;
        if (siz[x] > siz[y]) {
            swap(x, y);
        }
        sef[x] = y;
        siz[y] += siz[x];
    }
}
int main()
{
    FILE *fin, *fout;
    int n, m, i, x, y;
    fin = fopen("dfs.in", "r");
    fscanf(fin, "%d%d", &n, &m);
    for (i = 1; i <= n; i++) {
        sef[i] = i;
        siz[i] = 1;
    }
    nrc = n;
    for (i = 0; i < m; i++) {
        fscanf(fin, "%d%d", &x, &y);
        unesc(x, y);
    }
    fclose(fin);
    fout = fopen("dfs.out", "w");
    fprintf(fout, "%d\n", nrc);
    fclose(fout);
    return 0;
}