Cod sursa(job #2656603)

Utilizator modulopaulModulopaul modulopaul Data 8 octombrie 2020 08:48:22
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.76 kb
#include <iostream>
#include <fstream>

using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
int n,m,viz[100005],cnt;
typedef struct nod{
    int x;
    nod *urm;
} *pnod;
pnod v[100005];
void add(pnod &dest,int val){
    pnod p=new nod;
    p->x=val;
    p->urm=dest;
    dest=p;
}
void citire(){
    fin>>n>>m;
    for(int i=1;i<=m;i++){
        int x,y;
        fin>>x>>y;
        add(v[x],y);
        add(v[y],x);
    }
}
void DFS(int nd){
    pnod p;
    viz[nd]=1;
    for(p=v[nd];p!=NULL;p=p->urm)
        if(!viz[p->x])
            DFS(p->x);
}
int main()
{
    citire();
    for(int i=1;i<=n;i++){
        if(!viz[i]){
            cnt++;
            DFS(i);
        }
    }
    fout<<cnt;
    return 0;
}