Cod sursa(job #3277632)

Utilizator xndrxwPascal Andrei xndrxw Data 16 februarie 2025 22:57:01
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.83 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
#define cin fin
#define cout fout
long long n,m,p,viz[1000001];

struct nod{
    int vf;
    nod *urm;
} *v[1000001];

void adaugare(nod *&prim, int x){
    nod *nou = new nod;
    nou->vf = x;
    nou->urm=prim;
    prim=nou;
}

void citire(){
    cin>>n>>m;
    int x,y;
    for(int i=1;i<=m;i++){
        cin>>x>>y;
        adaugare(v[x],y);
        adaugare(v[y],x);
    }
}

void dfs(int x){
    viz[x]=1;
    for(nod* p=v[x];p;p=p->urm){
            if(viz[p->vf]==0){
                dfs(p->vf);
            }
        }
}

int main()
{
    citire();
    int k=0;
    for(int i=1;i<=n;i++){
        if(!viz[i]){
            k++;
            dfs(i);
        }
    }
    cout<<k;
    return 0;
}