/**
    3. Write a program that finds the connected components of an undirected graph using a depth-first traversal of the graph.
    4. Write a program that finds the connected components of an undirected graph using a breadth-first traversal of the graph.

    2B. Write a program that finds the biconnected components of an undirected graph in O(n+m).
*/

#include <iostream>
#include <queue>
#include <fstream>
#include <vector>

using namespace std;

/**
    UndirectedGraph class to encapsulate the data for a graph.
    Contains:
        the neighbours list for each vertex

*/
class UndirectedGraph {
public:
    UndirectedGraph() {
    }
    UndirectedGraph(string fileName) {
        ifstream fin(fileName.c_str());
        fin >> this->vertices >> this->edges;
        this->g.resize(vertices);
        for(int i = 0 ; i < this->edges; ++ i) {
            int x, y;
            fin >> x >> y;
            -- x;
            -- y;
            this->addEdge(x, y);
        }
    }
    bool isEdge(int x, int y) {
        for(auto it : g[x])
            if(it == y)
                return 1;
        return 0;
    }
    void addEdge(int x, int y) {
        if(isEdge(x, y))
            return ;
        this->edges ++;
        this->g[x].push_back(y);
    }
    int getNoVertices() {
        return this->vertices;
    }
    int getNoEdges() {
        return this->edges;
    }
    vector <vector <int> > getConnectedComponentsDfs() {
        vector <vector <int> > cc;
        vector <bool> visited(this->vertices, false);
        for(int i = 0 ; i < this->vertices ; ++ i)
            if(!visited[i]) {
                vector <int> act;
                _dfs(i, visited, act);
                cc.push_back(act);
            }
        return cc;
    }
    vector <vector <int> > getConnectedComponentsBfs() {
        vector <bool> visited(this->vertices, false);
        vector <vector <int> > cc;
        for(int i = 0 ; i < this->vertices ; ++ i)
            if(!visited[i]) {
                vector <int> act;
                _bfs(i, visited, act);
                cc.push_back(act);
            }
        return cc;
    }
    UndirectedGraph deepCopy() {
        UndirectedGraph newg;
        newg.vertices = this->vertices;
        newg.edges = this->edges;
        newg.g = this->g;
        return newg;
    }
private:
    void _dfs(int node, vector <bool> &visited, vector <int> &act) {
        visited[node] = 1;
        act.push_back(node);
        for(auto it : g[node])
            if(!visited[it])
                _dfs(it, visited, act);
    }
    void _bfs(int stnode, vector <bool> &visited, vector <int> &act) {
        queue <int> q;
        q.push(stnode);
        visited[stnode] = 1;
        while(!q.empty()) {
            int node = q.front();
            act.push_back(node);
            q.pop();
            for(auto it : g[node])
                if(!visited[it]) {
                    visited[it] = 1;
                    q.push(it);
                }
        }
    }
    vector <vector <int>> g;
    int vertices, edges;
};

int main() {
    UndirectedGraph g("dfs.in");
    ofstream fout("dfs.out");
    fout << g.getConnectedComponentsBfs().size() << '\n';
}