Cod sursa(job #2763016)

Utilizator Teodor_AxinteAxinte Teodor-Ionut Teodor_Axinte Data 11 iulie 2021 09:00:29
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.31 kb
#include <fstream>
#include <iostream>
#include <bitset>

using namespace std;

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

struct nodd {
    int value;
    nodd *next;
};


void add_begin(nodd *&L, int integer) {
    nodd *aux = new nodd;
    aux->value = integer;
    aux->next = L;
    L = aux;
}

void display(nodd *L) {
    while (L != nullptr) {
        fout << L->value << " ";
        L = L->next;
    }

    fout << endl;
}

int n, m, ct;
bitset<100010> viz;

void dfs(int);

nodd *L[] ={};

int main() {

    fin >> n >> m;


    for (; m != 0; m--) {
        int x, y;
        fin >> x >> y;
        add_begin(L[x], y);
        add_begin(L[y], x);
    }
/*
    display(L[1]);
    display(L[2]);
    display(L[3]);
    display(L[4]);
    display(L[5]);

    fout<<endl<<endl;

    for(int i=1;i<=5;i++) {

        while (L[i] != nullptr) {
            fout << L[i]->value;
            L[i] = L[i]->next;
        }
    fout<<endl;
    }
*/

    for (int i = 1; i <= n; i++)
        if (!viz[i]) {
            viz[i] = true;

            dfs(i);
            ct++;
        }


    //fout<<"am trecut de for\n";

    fout << ct;

    return 0;
}

void dfs(int nod_cur) {
    while (L[nod_cur] != nullptr) {
        viz[L[nod_cur]->value] = true;
        L[nod_cur] = L[nod_cur]->next;
        dfs(L[nod_cur]->value);
    }
}