Cod sursa(job #2369161)

Utilizator alex.sirbuSirbu Alexandru alex.sirbu Data 5 martie 2019 21:30:20
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.81 kb
#include <iostream>
#include <fstream>
#define MAX 100001
using namespace std;

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

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

pNod v[MAX];
int n, m;
bool vizitat[MAX];

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

void read(){
    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 nod){
    pNod p;
    vizitat[nod]=true;
    for(p=v[nod]; p!=NULL; p=p->a)
        if(!vizitat[p->x])
            DFS(p->x);
}

int main()
{
    read();
    int cont=0;
    for(int i=1; i<=n; i++)
        if(!vizitat[i]){
            cont++;
            DFS(i);
        }
    fout<<cont;
}