Cod sursa(job #2960553)

Utilizator Teodor11Posea Teodor Teodor11 Data 4 ianuarie 2023 17:32:34
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.53 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

const int MAX_SIZE = 100001;
vector<int> neighbors[MAX_SIZE];
int n, m, visited[MAX_SIZE], cnt;

void graph_traversal(int node) {
    visited[node] = 1;
    /*
    cout << "Nodul curent este nodul \"" << node << "\"\n";
    cout << "Nodurile marcate sunt: ";
    for (int i = 1; i <= n; ++i) {
        cout << '[' << i << "] " << visited[i] << ' ';
    }
    cout << '\n';
    */
    int curr_neighbors_num = neighbors[node].size();
    for (int i = 0; i < curr_neighbors_num; ++i) {
        if (!visited[neighbors[node][i]]) {
            //cout << "Ne deplasam la nodul \"" << neighbors[node][i] << "\"\n\n";
            graph_traversal(neighbors[node][i]);
        }
    }
}

int main() {
    ifstream fin("dfs.in");
    ofstream fout("dfs.out");
    fin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int x, y;
        fin >> x >> y;
        neighbors[x].push_back(y);
        neighbors[y].push_back(x);
    }
    /*
    for (int i = 1; i <= n; ++i) {
        cout << "Vecinii nodului " << i << " sunt: ";
        for (int j = 0; j < neighbors[i].size(); ++j) {
            cout << neighbors[i][j] << ' ';
        }
        cout << '\n';
    }
    */
    for (int i = 1; i <= n; ++i) {
        if (!visited[i]) {
            graph_traversal(i);
            ++cnt;
            //cout << "Nodul " << i << " este nodul sursa al componentei conexe cu numarul " << cnt << '\n';
        }
    }
    fout << cnt;
    return 0;
}