Cod sursa(job #3262702)

Utilizator BuruianaRaresAndreiBuruiana Rares Andrei BuruianaRaresAndrei Data 11 decembrie 2024 13:19:50
Problema Parcurgere DFS - componente conexe Scor 0
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[105], ans[105];
bitset<105> 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;
    int u, v;
    while(in >> u >> v) {
        // out << u << ' ' << v << '\n';
        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;
}