Cod sursa(job #3308209)

Utilizator alesiodemiriAlesio Demiri alesiodemiri Data 23 august 2025 17:12:25
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.5 kb
#include <iostream>
#include <queue>
#include <algorithm>
#include <set>
#include <map>
#include <stack>
#include <vector>
#include <string>
#include <deque>
#include <unordered_map>
#include <unordered_set>
#include <cmath>
#include <iomanip>

using namespace std;

#define ll long long

int n, m;
vector<vector<int>> graph;


void ReadData() {
    cin >> n >> m;
    
    graph.assign(n, vector<int>());

    for (int i = 0; i < m; i++) {
        int start = 0;
        int end = 0;
        cin >> start >> end;
        start--; end--;
        graph[start].push_back(end);
        graph[end].push_back(start);
    }
    
}

void Solve() {
    vector<bool> visited (n, false);
    int result = 0;

    for(int i = 0; i < n; ++i){
        if (!visited[i]){
            result++;

            stack<int> q;
            q.push(i);
            visited[i] = true;

            while (!q.empty()){
                int val = q.top(); q.pop();
                for(int neighbour: graph[val]){
                    if (!visited[neighbour]){
                        visited[neighbour] = true;
                        q.push(neighbour);
                    }
                }
            } 
        } 
    } 
    cout << result << "\n";
    return;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    freopen("dfs.in", "r", stdin);
    freopen("dfs.out", "w", stdout);

    int t = 1;
    // cin >> t; // Uncomment for multiple test cases
    while (t--) {
        ReadData();
        Solve();   
    }
    return 0;
}