Cod sursa(job #2961498)

Utilizator Teodor11Posea Teodor Teodor11 Data 6 ianuarie 2023 16:25:09
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.56 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

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

void conex_component_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 node_neighbors = neighbors[node].size();
    for (int i = 0; i < node_neighbors; ++i) {
        if (!visited[neighbors[node][i]]) {
            //cout << "Ne deplasam la nodul \"" << neighbors[node][i] << "\"\n\n";
            conex_component_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]) {
            conex_component_traversal(i);
            ++cnt;
            //cout << "Nodul " << i << " este nodul sursa al componentei conexe cu numarul " << cnt << '\n';
        }
    }
    fout << cnt;
    return 0;
}