Cod sursa(job #3121896)

Utilizator indianu_talpa_iuteTisca Catalin indianu_talpa_iute Data 15 aprilie 2023 23:40:17
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;

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

vector<vector<int>> adj;
bitset<MAXN> visited;

void read() {
    int n, m;
    fin >> n >> m;
    adj = vector<vector<int>>(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);
    }
}

void dfs(int start) {
    visited[start] = true;
    for (auto& neighbour: adj[start])
        if (!visited[neighbour])
            dfs(neighbour);
}

int solve() {
    int count = 0;
    for (int node = 0; node < adj.size(); node++) {
        if (visited[node])
            continue;
        count++;
        dfs(node);
    }
    return count;
}

int main() {
    read();
    fout << solve();
    return 0;
}