#include <fstream>
#include <list>
#include <vector>
using namespace std;
#ifndef __GRAPH__H
#define __GRAPH__H
// Structura Node este utila doar pentru implementarea cu liste de vecini
struct Node
{
std::vector<int> neighbors;
};
class Graph {
private:
std::vector<Node> nodes; // Implementare cu liste de vecini
// int **adiacency_matrix; // Implementare cu matrice de adiacenta
public:
Graph(int size)
{
nodes = vector<Node>(size);
}
~Graph()
{
}
//void add_node(int node); // Atentie: pentru implementarea cu matrice
//void remove_node(int node); // puteti ignora aceaste doua functii
void add_edge(int src, int dst)
{
if(nodes[src].neighbors.size() == 0){
nodes[src].neighbors.push_back(-1);
nodes[dst].neighbors.push_back(-1);
nodes[src].neighbors.push_back(dst);
nodes[dst].neighbors.push_back(src);
} else {
nodes[src].neighbors.push_back(dst);
nodes[dst].neighbors.push_back(src);
}
}
void remove_edge(int src, int dst)
{
int i;
for (i = 0; i < nodes[src].neighbors.size(); i++)
if (nodes[src].neighbors[i] == dst)
nodes[src].neighbors.erase(nodes[src].neighbors.begin() + i);
for (i = 0; i < nodes[dst].neighbors.size(); i++)
if (nodes[dst].neighbors[i] == src)
nodes[dst].neighbors.erase(nodes[dst].neighbors.begin() + i);
}
bool has_edge(int src, int dst)
{
int i;
for (i = 0; i < nodes[src].neighbors.size(); i++)
if (nodes[src].neighbors[i] == dst)
return true;
return false;
}
std::vector<int> get_neighbors(int node)
{
return nodes[node].neighbors;
}
};
#endif //__GRAPH__H
void dfs(Graph &g, int node, vector<int> &viz)
{
if(viz[node])
return;
viz[node] = 1;
for (int i = 1; i < g.get_neighbors(node).size(); i++) {
if(viz[g.get_neighbors(node)[i]] == 0){
dfs(g, g.get_neighbors(node)[i], viz);
}
}
}
int main()
{
int m, n, a, b;
int counter = 0;
ifstream f("dfs.in");
ofstream o("dfs.out");
f >> n >> m;
Graph g(n + 1);
vector<int> viz(n + 1, 0);
for (int i = 0; i < m; i++)
{
f >> a >> b;
g.add_edge(a, b);
}
for (int j = 1; j <= n; j++) {
if(viz[j] == 0){
dfs(g, j, viz);
counter++;
}
}
o << counter;
f.close();
o.close();
return 0;
}