Cod sursa(job #3224353)

Utilizator tricksteryetiGeorge Popa tricksteryeti Data 15 aprilie 2024 11:13:32
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.12 kb
#include <iostream>
#include <vector>

using namespace std;

void dfs(int node, vector<bool>& visited, vector<vector<int>>& graph) {
    visited[node] = true;
    for (int neighbor : graph[node]) {
        if (!visited[neighbor]) {
            dfs(neighbor, visited, graph);
        }
    }
}

int countConnectedComponents(vector<vector<int>>& graph) {
    int n = graph.size();
    vector<bool> visited(n, false);
    int count = 0;

    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            dfs(i, visited, graph);
            count++;
        }
    }

    return count;
}

int main() {
    int n, m;
    ifstream inputFile("dfs.in");
    ofstream outputFile("dfs.out");


    int n;
    inputFile >> n;
    int m;
    inputFile >> m;

    vector<vector<int>> graph(n);

    for (int i = 0; i < m; i++) {
        int u, v;
        inputFile >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    int numComponents = countConnectedComponents(graph);
    outputFile<< numComponents;

    inputFile.close();
    outputFile.close();

    return 0;
}