#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#define size 100000
int visited[size] = { 0 };
typedef struct vertex
{
    int name;
    int numNeighbours;
    struct vertex** neighbours;
} vertex;

typedef struct GraphVertex
{
    int numNodes;
    int numEdges;
    vertex* nodes;
} GraphVertex;

GraphVertex ReadFile()
{
    FILE* fptr = fopen("dfs.in", "r");
    GraphVertex graph;
    fscanf(fptr, "%d %d", &graph.numNodes, &graph.numEdges);
    graph.nodes = (vertex*)malloc(graph.numNodes * sizeof(vertex));

    for (int i = 0; i < graph.numNodes; i++)
    {
        graph.nodes[i].numNeighbours = 0;
        graph.nodes[i].neighbours = NULL;
        graph.nodes[i].name = i + 1;
    }
    int aux = graph.numEdges;
    int left, right;
    while (aux)
    {
        fscanf(fptr, "%d %d", &left, &right);
        graph.nodes[left - 1].neighbours = (vertex**)realloc(graph.nodes[left - 1].neighbours, (graph.nodes[left - 1].numNeighbours + 1) * sizeof(vertex*));
        graph.nodes[left - 1].neighbours[graph.nodes[left - 1].numNeighbours] = graph.nodes + (right - 1);
        graph.nodes[right - 1].neighbours = (vertex**)realloc(graph.nodes[right - 1].neighbours, (graph.nodes[right - 1].numNeighbours + 1) * sizeof(vertex*));
        graph.nodes[right - 1].neighbours[graph.nodes[right - 1].numNeighbours] = graph.nodes + (left - 1);
        graph.nodes[left - 1].numNeighbours++;
        graph.nodes[right - 1].numNeighbours++;
        aux--;
    }

    fclose(fptr);
    return graph;
}
void DFS(GraphVertex graph, int current)
{
    visited[current] = 1;
    for (int i = 0; i < graph.nodes[current].numNeighbours; i++)
    {
        if (!visited[graph.nodes[current].neighbours[i]->name - 1])
            DFS(graph, graph.nodes[current].neighbours[i]->name - 1);
    }
}
int main()
{
    GraphVertex graph = ReadFile();
    int componente = 0;
    for (int i = 0; i < graph.numNodes; i++)
    {
        if (!visited[i])
        {
            DFS(graph, i);
            componente++;
        }
    }
    FILE* out = fopen("dfs.out", "w");
    fprintf(out, "%d", componente);
    fclose(out);

    return 0;
}