Cod sursa(job #3314390)

Utilizator dumy123Darius Dumitrascu dumy123 Data 9 octombrie 2025 22:05:12
Problema Parcurgere DFS - componente conexe Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.18 kb
#include <iostream>
#include <fstream>
std::ifstream fin("dfs.in");
std::ofstream fout("dfs.out");
int main(){
    int n,m,x,y,nr=0;
    fin>>n>>m;
    int viz[100001]={0},vecini[100001]={0};
    while(m){
        fin>>x>>y;
        if(viz[x]==0 && viz[y]==0){
            nr++;
            viz[x]=1;
            vecini[x]=nr;
            viz[y]=1;
            vecini[y]=nr;
        }
        if(viz[x]==0 && viz[y]!=0){
            viz[x]=1;
            vecini[x]=vecini[y];
        }
        if(viz[x]!=0 && viz[y]==0){
                viz[y]=1;
                vecini[y]=vecini[x];
            }
        if(viz[x]!=0 && viz[y]!=0 && vecini[x]!=vecini[y])
        {
            for(int i=1;i<=n;i++){
                if(vecini[i]==vecini[y]){
                    vecini[i]=vecini[x];
                }
            }
            nr--;
        }
        m--;
    }
    // for(int i=1;i<=n;i++){
    //     std::cout<<viz[i]<<" ";
    // }
    // std::cout<<std::endl;
    // for(int i=1;i<=n;i++){
    //     std::cout<<vecini[i]<<" ";
    // }
    for(int i=1;i<=n;i++){
        if(viz[i]==0){
            nr++;
        }
    }
    fout<<nr;   
    return 0;
}