Cod sursa(job #2139449)

Utilizator KazvikKokovics Razvan Kazvik Data 22 februarie 2018 16:00:55
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include<fstream>
#define NMAX 100005

using namespace std;

ifstream in("dfs.in");
ofstream out("dfs.out");

int n,m,viz[NMAX],nr;

typedef struct nod{
    int x;
    nod *a;
}*pNod;

pNod v[NMAX];

void add(pNod &dest,int val){
    pNod p;
    p=new nod;
    p->x=val;
    p->a=dest;
    dest=p;
}

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

void DFS(int nod){
    pNod p;
    viz[nod]=1;
    for(p=v[nod];p!=NULL;p=p->a)
        if(viz[p->x]==0)
            DFS(p->x);
}

int main()
{
    citire();
    int i;
    for(i=1;i<=n;i++)
        if(!viz[i]){
            nr++;
            DFS(i);
        }
    out<<nr;
    return 0;
}