Pagini recente » Cod sursa (job #3326339) | Cod sursa (job #3328395) | Cod sursa (job #2314070) | Cod sursa (job #3318437) | Cod sursa (job #3333432)
#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;
}