Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- int n, m;
- vector<bool> visited;
- vector<vector<int>> gr;
- void dfs(int u) {
- visited[u] = true;
- for (int to : gr[u]) {
- if (!visited[to]) {
- dfs(to);
- }
- }
- }
- int main() {
- cin >> n >> m;
- visited.assign(n+1, false);
- gr.assign(n+1, vector<int>());
- int a, b;
- for (int i = 0; i < m; ++i) {
- cin >> a >> b;
- gr[a].push_back(b);
- gr[b].push_back(a);
- }
- int cnt = 0;
- for (int u = 1; u <= n; ++u) {
- if (!visited[u]) {
- ++cnt;
- dfs(u);
- }
- }
- cout << cnt << '\n';
- }
Advertisement
Add Comment
Please, Sign In to add comment