#include <fstream>
#include <vector>
#include <iostream>
using namespace std;
///// DESCRIPTION
// THIS PROGRAM EMPLOYS DEPTH-FIRST SEARCH
// ON AN INPUT OF AN UNDIRECTED GRAPH
// WITH N VERTICES AND M EDGES
// TO DETERMINE HOW MANY
// CONNECTED COMPONENTS IT HAS
/////
void dfs(int, vector<int>[], bool[]);
int main(int argc, char **argv)
{
// INPUT
ifstream indata("dfs.in");
int n, m;
indata >> n >> m;
vector<int> edges[n + 1];
for (int i = 0, x, y; i < m; i++) {
indata >> x >> y;
// there is a path from x to y
// and from y to x
edges[x].push_back(y);
edges[y].push_back(x):
}
indata.close();
// DFS
bool visited[n + 1];
for (int i = 1; i <= n; i++) {
visited[i] = false;
}
int connectedComponents = 0;
for (int i = 1; i <= n; i++) {
if (visited[i] == true) {
continue;
}
// if this node has not been visited
// by doing dfs on another one already
// then it belongs to a different
// connected element
connectedComponents++;
// mark every node in this connected
// element as visited
dfs(i, edges, visited);
}
// OUTPUT
ofstream outdata("dfs.out");
outdata << connectedComponents;
outdata.close();
return 0;
}
void dfs(int currentNode, vector<int> edges[], bool visited[]) {
// mark current node as visited
visited[currentNode] = true;
// add all unvisited nodes to the stack
for (size_t i = 0; i < edges[currentNode].size(); i++) {
if (visited[edges[currentNode][i]] == false) {
dfs(edges[currentNode][i], edges, visited);
}
}
}