Pagini recente » Cod sursa (job #1753297) | Cod sursa (job #1240141) | Cod sursa (job #1386278) | Cod sursa (job #2387685) | Cod sursa (job #2777198)
//
// Created by Andrei Covaci on 03.09.2021.
//
#include <fstream>
#include <iostream>
#include <vector>
#include <stack>
#define INPUT "dfs.in"
#define OUTPUT "dfs.out"
//#define INPUT "input.in"
//#define OUTPUT "output.out"
using namespace std;
vector<vector<int>> read() {
ifstream in(INPUT);
int n, m, tail, head;
in >> n >> m;
vector<vector<int> > list;
list.reserve(n);
for(int i = 0; i < n; ++i) {
list.emplace_back();
}
for(int i = 0; i < m; ++i) {
in >> tail >> head;
tail--;
head--;
list[tail].push_back(head);
list[head].push_back(tail);
}
in.close();
return list;
}
int solve(vector<vector<int>>& list) {
vector<bool> visited;
visited.reserve(list.size());
for(int i = 0; i < list.size(); ++i) {
visited.push_back(false);
}
int cnt = 0;
for(int i = 0; i < list.size(); ++i) {
if (!visited[i]) {
cnt++;
stack<int> s;
s.push(i);
while(!s.empty()) {
int curr = s.top();
s.pop();
for(auto e : list[curr]) {
if(!visited[e]) {
s.push(e);
visited[e] = true;
}
}
}
}
}
return cnt;
}
void print(int c) {
ofstream out(OUTPUT);
out << c;
out.close();
}
int main() {
auto nums = read();
auto res = solve(nums);
print(res);
return 0;
}