Cod sursa(job #3314583)

Utilizator tudor_bustanBustan Tudor Gabriel tudor_bustan Data 10 octombrie 2025 13:48:18
Problema Parcurgere DFS - componente conexe Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.81 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");

int height[100005], viz[100005], nodes[100005], x, y, n, m, cc;
int fnd(int x){
    if(x==viz[x])return x;
    return fnd(viz[x]);
}
void unite(int a, int b){
    a=fnd(a);
    b=fnd(b);
    if(height[a]>height[b]){
        viz[b]=a;
        nodes[a]+=nodes[b];
    }
    else{
        viz[a]=b;
        nodes[b]+=nodes[a];
    }
    if(height[a]==height[b]){
        height[b]++;
    }
}
int main()
{
    fin>>n>>m;
    cc=n;
    for(int i=1; i<=n; i++){
        viz[i]=i;
        height[i]=1;
        nodes[i]=1;
    }
    for(int i=1; i<=m; i++){
        fin>>x>>y;
        if(viz[x]!=viz[y]){
            unite(x, y);
            cc--;
        }
    }
    fout<<cc;
    return 0;
}