Cod sursa(job #2923895)

Utilizator Teodor11Posea Teodor Teodor11 Data 20 septembrie 2022 18:18:14
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.68 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

vector<int> neighbors_list[100000];
int n, m, x, y, list_size[100000], visited_node[100000], cc_counter;

void DFS(int node) {
    if (visited_node[node]) {
        return;
    }
    visited_node[node] = 1;
    /*
    cout << "Nodul curent este nodul \"" << node + 1 << "\"\n";
    cout << "Nodurile marcate sunt: ";
    for (int i = 0; i < n; ++i) {
        cout << '[' << i + 1 << "] " << visited_node[i] << ' ';
    }
    cout << '\n';
    */
    for (int i = 0; i < list_size[node]; ++i) {
        //cout << "Ne deplasam la nodul \"" << neighbors_list[node][i] << "\"\n\n";
        DFS(neighbors_list[node][i] - 1);
    }
}

int main() {
    ifstream fin("dfs.in");
    ofstream fout("dfs.out");
    fin >> n >> m;
    for (int i = 0; i < m; ++i) {
        fin >> x >> y;
        neighbors_list[x - 1].push_back(y);
        neighbors_list[y - 1].push_back(x);
        ++list_size[x - 1];
        ++list_size[y - 1];
    }
    /*
    for (int i = 0; i < n; ++i) {
        cout << "Vecinii nodului " << i + 1 << " sunt: ";
        for (int j = 0; j < list_size[i]; ++j) {
            cout << neighbors_list[i][j] << ' ';
        }
        cout << "\n\n";
    }
    */
    for (int i = 0; i < n; ++i) {
        if (!visited_node[i]) {
            //cout << "Pentru nodul " << i + 1 << ": ";
            DFS(i);
            ++cc_counter;
            /*
            for (int j = 0; j < n; ++j) {
                cout << '[' << j + 1 << "] " << visited_node[j] << ' ';
            }
            cout << "\n\n";
            */
        }
    }
    fout << cc_counter;
    return 0;
}