L5Q2

// Grafos - Lista de adjacência

#include <iostream>
#include <list>
#include <queue>

using namespace std;

const int tamanho_maximo = 1000;

bool visitados[tamanho_maximo];
int contador;

class Grafo {
    int V; // número de vértices
    list<int> *adj; // ponteiro para um array contendo as listas de adjacências

public:
    Grafo(int V) {
        this->V = V; // atribui o número de vértices
        adj = new list<int>[V]; // cria as listas
    }

    void adicionarAresta(int v1, int v2) {
        // adiciona vértice v2 à lista de vértices adjacentes de v1
        adj[v1].push_back(v2);
        adj[v2].push_back(v1);
    }

    void resetar_visitados() {
        for(int i = 0; i < V; i++)
            visitados[i] = false;
    }

    void bfs(int v) {
        queue<int> fila;

        visitados[v] = true; // marca como visitado

        while(true) {
            list<int>::iterator it;
            for(it = adj[v].begin(); it != adj[v].end(); it++) {
                if(!visitados[*it]) {
                    visitados[*it] = true; // marca como visitado
                    fila.push(*it); // insere na fila
                }
            }
            // verifica se a fila NÃO está vazia
            if (!fila.empty()) {
                v = fila.front(); // obtém o primeiro elemento
                fila.pop(); // remove da fila
            } else {
                return;
            }
        }
    }
};


int main() {
    int quantidade;
    cin >> quantidade;
    for (int i = 0; i < quantidade; i++) {
        char vertices;
        cin >> vertices;
        int vertices2 = vertices - 'A' + 1;
        Grafo grafo(vertices2);
        int v1, v2;
        string arestabranco;
        getline(cin,arestabranco);
        do {
            string aresta;
            getline(cin,aresta);
            if (aresta == "")
                break;
            v1 = aresta[0] - 'A';
            v2 = aresta[1] - 'A';
            grafo.adicionarAresta(v1, v2);
        } while (true);
        grafo.resetar_visitados();
        for (int j = 0; j < vertices2 ; j++) {
            if (visitados[j] == false){
                contador+=1;
                grafo.bfs(j);
            }
        }
        if(i==quantidade-1){
            cout << contador;
            contador = 0;
        } else {
            cout << contador << endl;
            contador = 0;
        }


    }
    return 0;
}