Cod sursa(job #3262703)

Utilizator BuruianaRaresAndreiBuruiana Rares Andrei BuruianaRaresAndrei Data 11 decembrie 2024 13:20:54
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.07 kb
#include <bits/stdc++.h>

using namespace std;

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

int n, m, start, nrCompConex;
vector<int> g[100005], ans[100005];
bitset<100005> used;

void dfs(int node) {
    used[node] = true;
    ans[nrCompConex].push_back(node);
    for(auto nxt : g[node])
        if(!used[nxt])
            dfs(nxt);
}

int main() {
    in >> n >> m;
    int u, v;
    for(int i = 1; i <= m; i++) {
        in >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    /*
    out << n << '\n';
    for(int i = 1; i <= n; i++) {
        for(auto elem : g[i])
            out << elem << ' ';
        out << '\n';
    }
    */
    for(int i = 1; i <= n; i++) {
        if(!used[i]) {
            nrCompConex++;
            dfs(i);
            sort(ans[nrCompConex].begin(), ans[nrCompConex].end());
        }
    }
    out << nrCompConex << '\n';
    /*
    for(int i = 1; i <= nrCompConex; i++) {
        for(auto elem : ans[i])
            out << elem << ' ';
        out << '\n';
    }
    */
    return 0;
}