Cod sursa(job #2984665)

Utilizator GabiTulbaGabi Tulba-Lecu GabiTulba Data 24 februarie 2023 17:03:50
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.8 kb
#include <cstdio>
#include <vector>

using namespace std;

const int N_MAX = 100000;

int n, m, nr_comp = 0;
vector<int> G[N_MAX + 1];
vector<bool> is_visited;

void DFS(int node) {
    is_visited[node] = true;

    for (unsigned int i = 0; i < G[node].size(); i++) {
        if (!is_visited[G[node][i]]) {
            DFS(G[node][i]);
        }
    }
}

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

    scanf("%d%d", &n, &m);
    is_visited.resize(n + 1, false);

    for (int i = 1; i <= m; i++) {
        int x, y;

        scanf("%d%d", &x, &y);

        G[x].push_back(y);
        G[y].push_back(x);
    }

    for (int i = 1; i <= n; i++) {
        if (!is_visited[i]) {
            nr_comp++;
            DFS(i);
        }
    }

    printf("%d\n", nr_comp);

    return 0;
}