Cod sursa(job #2078974)

Utilizator NicolaalexandraNicola Alexandra Mihaela Nicolaalexandra Data 30 noiembrie 2017 12:58:19
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include <fstream>
#include <vector>
#define DIM 100001
using namespace std;
struct nod {
    int info;
    nod *urm;
};

int p,u,i,j,x,y,v[DIM],c[DIM],S,vecin,n,m,ap;

nod *L[100001];/// vextor cu 100000 de pointeri, p-urile de la fiecare lista d vecini

void dfs (int nd){
    v[nd]  = 1;
    for (nod *r = L[nd]; r!=NULL; r = r->urm)
        if (v[ r->info ] == 0)
            dfs ( r->info );

}
ifstream fin ("dfs.in");
ofstream fout ("dfs.out");
int main (){

    fin>>n>>m;
    for (i=1;i<=m;i++){
        fin>>x>>y;
        nod *r = new nod;
        r->info = x;
        r->urm = L[y];
        L[y] = r;

        r = new nod;
        r->info = y;
        r->urm = L[x];
        L[x] = r;
    }

    for (i=1;i<=n;i++){
        if (v[i] == 0){
            ap++;
            dfs(i);
        }
    }
    fout<<ap;



    return 0;
}