Cod sursa(job #2723566)

Utilizator Florian11232Florian Susai Florian11232 Data 14 martie 2021 20:53:16
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.22 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

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

// numarul maxim de noduri
const int Nmax = 100005;

vector<int> graph[Nmax];
bool visited[Nmax];

void dfs(int node) {
    visited[node] = true;

    // parcurg toti vecinii y ai lui node
    for (int i = 0; i < graph[node].size(); i++) {
        int y = graph[node][i];
        if (!visited[y]) {
            dfs(y);
        }
    }
}

int main()
{
    int N, M, x, y, i;

    in >> N >> M;
    for (int i = 0; i < M; i++) {
        in >> x >> y;
        graph[x].push_back(y); // adaug in lista vecinilor lui x pe y
        graph[y].push_back(x); // adaug in lista vecinilor lui y pe x
    }

    // afisare lista vecini
    // for (int node = 1; node <= N; node++) {
    //     out << node << ": ";
    //     // parcurg toti vecinii lui node
    //     for (int y = 0; y < graph[node].size(); y++) {
    //         out << graph[node][y] << " ";
    //     }
    //     out << '\n';
    // }

    int nr = 0;
    for (i = 1; i <= N; i++) {
        if (!visited[i]) {
            nr++;
            dfs(i);
        }
    }

    out << nr << '\n';

    return 0;
}