Cod sursa(job #3294954)

Utilizator liviu0709Stoica Liviu liviu0709 Data 30 aprilie 2025 18:18:58
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.33 kb
#include <bits/stdc++.h>
#include <unordered_map>

using namespace std;

class Task {
    public:
    static constexpr int NMAX = 1e5 + 5;
    int n, m;
    int sol;
    vector<int> adj[NMAX];

    void citire() {
        FILE *in = fopen("dfs.in", "r");
        fscanf(in, "%d %d", &n, &m);
        for ( int i = 0 ; i < m ; i++ ) {
            int src, dst;
            fscanf(in, "%d %d", &src, &dst);
            adj[src].push_back(dst);
            adj[dst].push_back(src);
        }
    }

    unordered_map<int, bool> vizitat;
    int cnt = 0;
    bool progress;
    void dfs(int start) {
        if ( vizitat.find(start) != vizitat.end() )
            return;
        vizitat[start] = true;
        progress = true;
        cnt++;
        for ( int i = 0 ; i < adj[start].size() ; i++ ) {
            if ( vizitat.find(adj[start][i]) == vizitat.end() )
                dfs(adj[start][i]);
        }
    }

    void solve() {
        citire();
        for ( int i = 1 ; i <= n ; i++ ) {
            progress = false;
            dfs(i);
            if ( progress )
                sol++;
            if ( cnt == n )
                break;
        }
        scriere();
    }

    void scriere() {
        FILE *out = fopen("dfs.out", "w");
        fprintf(out, "%d", sol);
    }
};

int main() {
    auto* t = new Task();
    t->solve();
    delete t;
}