Cod sursa(job #3123742)

Utilizator AdoiePopa Adelin-Costin Adoie Data 25 aprilie 2023 10:42:12
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.03 kb
#include <bits/stdc++.h>
#include <fstream>
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

#define NMAX 100005

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

    int N, M;
    fin >> N >> M;

    vector<int> adj[NMAX];
    vector<bool> visited(NMAX, false);

    for (int i = 1, x, y; i <= M; i++) {
        fin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }

    fin.close();

    int nr_cc = 0;

    for (int i = 1; i <= N; i++) {
        if (!visited[i]) {
            nr_cc++;
            queue<int> q;
            q.push(i);
            visited[i] = true;
            while (!q.empty()) {
                int node = q.front();
                q.pop();
                for (auto neigh : adj[node]) {
                    if (!visited[neigh]) {
                        q.push(neigh);
                        visited[neigh] = true;
                    }
                }
            }
        }
    }

    fout << nr_cc << endl;

    fout.close();

    return 0;
}