Cod sursa(job #3123744)

Utilizator RyyyIsmana Robert Ryyy Data 25 aprilie 2023 10:44:28
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.91 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>

using namespace std;

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

int main(){

    int N, M;

    fin >> N >> M;

    for (int i = 0; i < M; i++){
        int x, y;
        fin >> x >> y;
    }

    // Find the number of connected components in the graph

    int nr = 0;

    vector<bool> visited(N + 1, false);
    queue<int> q;

    for (int i = 1; i <= N; i++){
        if (!visited[i]){
            nr++;
            q.push(i);
            visited[i] = true;

            while (!q.empty()){
                int node = q.front();
                q.pop();

                for (int neighbour : adj[node]){
                    if (!visited[neighbour]){
                        q.push(neighbour);
                        visited[neighbour] = true;
                    }
                }
            }
        }
    }

    fout << nr;
    



}