Cod sursa(job #3122129)

Utilizator indianu_talpa_iuteTisca Catalin indianu_talpa_iute Data 17 aprilie 2023 12:57:53
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.85 kb
#include <bits/stdc++.h>
#define MAXN 100000

using namespace std;
using bitmap = bitset<MAXN>;
using graph = vector<vector<int>>;

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

void dfs(graph& adj, int current, bitmap& checked) {
    checked[current] = true;
    for (auto& neighbour: adj[current])
        if (!checked[neighbour])
            dfs(adj, neighbour, checked);
}

int main() {
    int n, m;
    fin >> n >> m;
    graph adj(n, vector<int>());
    for (int i = 0; i < m; i++) {
        int iNode, jNode;
        fin >> iNode >> jNode;
        iNode--, jNode--;
        adj[iNode].push_back(jNode);
        adj[jNode].push_back(iNode);
    }

    int count = 0;
    bitmap checked;
    for (int i = 0; i < n; i++) {
        if (checked[i])
            continue;
        dfs(adj, i, checked);
        count++;
    }

    fout << count;
    return 0;
}