Cod sursa(job #3158308)

Utilizator RaicanMihaiRaican Mihai RaicanMihai Data 18 octombrie 2023 12:16:32
Problema Parcurgere DFS - componente conexe Scor 35
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.52 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <list>
#include <queue>
using namespace std;

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

void dfs(int node, vector <bool>& visited, vector<list<int>> adjacencyList) {
    
    visited[node] = true;

    for (int neighbor : adjacencyList[node]) {
        if (!visited[neighbor]) {
            dfs(neighbor, visited, adjacencyList);
        }
    }
}

vector<list<int>> from_edges_to_list (int n, list<pair<int, int>> edges) {

    vector<list<int>> adjacencyList;
    adjacencyList.resize(n + 1);
    for (auto p : edges) {
        adjacencyList[p.first].push_back(p.second);
        adjacencyList[p.second].push_back(p.first);
    }

    return adjacencyList;
}

int main() {
    int N, M;
    list <pair <int, int>> edges;
    fin >> N >> M;
    for (int i = 0; i < M; i++) {
        int x, y;
        fin >> x >> y;
        edges.push_back(make_pair(x, y));
    }

    // creez lista de adiacenta
    vector<list <int>> adjacencyList = from_edges_to_list(N, edges);

    // vectorul in care verific daca un nod a fost vizitat
    vector <bool> visited((N + 1), false);
    int counter = 0; // nr componente conexe

    // verific ce noduri au fost vizitate
    for (int i = 1; i <= N; i++) {
        // daca nodul i nu a fost vizitat, apelez dfs
        // si adaug inca o componenta conexa
        if (!visited[i]) {
            dfs(i, visited, adjacencyList);
            counter++;
        }
    }
    fout << counter;
}