Pagini recente » Cod sursa (job #3303549) | Cod sursa (job #3318407) | Cod sursa (job #3317162) | Cod sursa (job #3316872) | Cod sursa (job #3308209)
#include <iostream>
#include <queue>
#include <algorithm>
#include <set>
#include <map>
#include <stack>
#include <vector>
#include <string>
#include <deque>
#include <unordered_map>
#include <unordered_set>
#include <cmath>
#include <iomanip>
using namespace std;
#define ll long long
int n, m;
vector<vector<int>> graph;
void ReadData() {
cin >> n >> m;
graph.assign(n, vector<int>());
for (int i = 0; i < m; i++) {
int start = 0;
int end = 0;
cin >> start >> end;
start--; end--;
graph[start].push_back(end);
graph[end].push_back(start);
}
}
void Solve() {
vector<bool> visited (n, false);
int result = 0;
for(int i = 0; i < n; ++i){
if (!visited[i]){
result++;
stack<int> q;
q.push(i);
visited[i] = true;
while (!q.empty()){
int val = q.top(); q.pop();
for(int neighbour: graph[val]){
if (!visited[neighbour]){
visited[neighbour] = true;
q.push(neighbour);
}
}
}
}
}
cout << result << "\n";
return;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
freopen("dfs.in", "r", stdin);
freopen("dfs.out", "w", stdout);
int t = 1;
// cin >> t; // Uncomment for multiple test cases
while (t--) {
ReadData();
Solve();
}
return 0;
}