Cod sursa(job #2763009)

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

using namespace std;


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


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

void add_back(nodd *&L, int integer) {
    nodd *l = new nodd;
    l->value = integer;
    l->next = nullptr;

    if (L == nullptr)
        L = l;
    else {
        nodd *cop_L = L;
        while (cop_L->next != nullptr)
            cop_L = cop_L->next;
        cop_L->next = l;
    }
}

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

int n, m, ans;

bitset<100010> viz;

void dfs(int, nodd **);

int main() {
    fin >> n >> m;

    nodd **L = new nodd *[n + 10];

    for (int i = 1; i <= n; i++)
        L[i] = new nodd[n + 10];


    for (; m != 0; m--) {
        int x, y;
        fin >> x >> y;
        add_back(L[x], y);
        add_back(L[y], x);
    }


    for (int i = 1; i <= n; i++)
        if (!viz[i]) {
            ans++;
            viz[i] = true;
            dfs(i, L);
        }

    fout << ans;

    return 0;
}

void dfs(int nod_cur, nodd **L) {
    for (nodd *cop_L = L[nod_cur];cop_L!=nullptr; cop_L = cop_L->next)
        if (!viz[cop_L->value]) {
            viz[cop_L->value] = true;
            dfs(cop_L->value, L);
        }
}