Cod sursa(job #3230287)

Utilizator cristianc90210Cristian Constantin cristianc90210 Data 20 mai 2024 14:10:45
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.87 kb
//
// Created by Cristian Constantin on 20.05.2024.
//
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

const int MAXN = 100001;
ifstream fin("dfs.in");
ofstream fout("dfs.out");

vector<vector<int>> graph(MAXN);
vector<bool> visited(MAXN, false);
int nodes, edges, componentCount = 0;

void depthFirstSearch(int node) {
    visited[node] = true;
    for (int neighbor : graph[node]) {
        if (!visited[neighbor]) {
            depthFirstSearch(neighbor);
        }
    }
}

int main() {
    fin >> nodes >> edges;
    int u, v;

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

    for (int i = 1; i <= nodes; ++i) {
        if (!visited[i]) {
            componentCount++;
            depthFirstSearch(i);
        }
    }

    fout << componentCount << endl;

    return 0;
}