Cod sursa(job #3333432)

Utilizator gpl12Giulia gpl12 Data 13 ianuarie 2026 15:50:51
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.08 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <iostream>
#include <queue>

using namespace std;

// ifstream fin("apm2.in");
// ofstream fout("apm2.out");
//
// const int NMAX = 10005;
// const int LOGMAX = 15;
//
// struct Edge {
//     int u, v, w;
//     bool operator<(const Edge& other) const {
//         return w < other.w;
//     }
// };
//
// int n, m, q;
// vector<Edge> edges;
// int t[NMAX];
// vector<pair<int, int>> adj[NMAX];
// int up[NMAX][LOGMAX];
// int mx[NMAX][LOGMAX];
// int depth[NMAX];
//
// int find(int x) {
//     if (t[x] == x) return x;
//     return t[x] = find(t[x]);
// }
//
// void unite(int x, int y) {
//     int rx = find(x);
//     int ry = find(y);
//     if (rx != ry) t[rx] = ry;
// }
//
// void dfs(int u, int p, int w, int d) {
//     depth[u] = d;
//     up[u][0] = p;
//     mx[u][0] = w;
//
//     for (int i = 1; i < LOGMAX; i++) {
//         up[u][i] = up[up[u][i - 1]][i - 1];
//         mx[u][i] = max(mx[u][i - 1], mx[up[u][i - 1]][i - 1]);
//     }
//
//     for (auto& edge : adj[u]) {
//         int v = edge.first;
//         int cost = edge.second;
//         if (v != p) {
//             dfs(v, u, cost, d + 1);
//         }
//     }
// }
//
// int solve(int u, int v) {
//     int ans = 0;
//     if (depth[u] < depth[v]) swap(u, v);
//
//     for (int i = LOGMAX - 1; i >= 0; i--) {
//         if (depth[u] - (1 << i) >= depth[v]) {
//             ans = max(ans, mx[u][i]);
//             u = up[u][i];
//         }
//     }
//
//     if (u == v) return ans;
//
//     for (int i = LOGMAX - 1; i >= 0; i--) {
//         if (up[u][i] != up[v][i]) {
//             ans = max(ans, mx[u][i]);
//             ans = max(ans, mx[v][i]);
//             u = up[u][i];
//             v = up[v][i];
//         }
//     }
//
//     ans = max(ans, mx[u][0]);
//     ans = max(ans, mx[v][0]);
//
//     return ans;
// }
//
// int main() {
//     fin >> n >> m >> q;
//
//     for (int i = 0; i < m; i++) {
//         int u, v, w;
//         fin >> u >> v >> w;
//         edges.push_back({u, v, w});
//     }
//
//     sort(edges.begin(), edges.end());
//
//     for (int i = 1; i <= n; i++) t[i] = i;
//
//     for (const auto& e : edges) {
//         if (find(e.u) != find(e.v)) {
//             unite(e.u, e.v);
//             adj[e.u].push_back({e.v, e.w});
//             adj[e.v].push_back({e.u, e.w});
//         }
//     }
//
//     dfs(1, 1, 0, 0);
//
//     for (int i = 0; i < q; i++) {
//         int x, y;
//         fin >> x >> y;
//         fout << solve(x, y) - 1 << "\n";
//     }
//
//     return 0;
// }
//ex1 DFS
const int NMAX = 10005;
std::queue<int> q;
std::vector<int> adj[NMAX];
bool viz[NMAX];

void dfs(int s) {
    viz[s]=true;
    for(int vecin: adj[s]) {
        if (!viz[vecin]){ dfs(vecin);}
    }
}
int main() {
    int n,m;
    cin>>n>>m;
    for (int i=1; i<=m; i++) {
        int x,y;
        cin>>x>>y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    int nr=0;
    for (int i=1; i<=n; i++) {
        if (!viz[i]) {
            nr++;
            dfs(i);
        }
    }
    cout<<nr; //nr comp coneze neorientat
    return 0;

}