Optymalizacja szybkości rozwiązania zadania

Mam takie zadanie:
Do klasy informatycznej uczęszcza n osób, z których każda posiada telefon komórkowy. Niektórzy wymienili się już swoimi numerami. Wychowawczyni zastanawia się, czy osoba x zdoła przekazać informację osobie y. Osoba x może dzwonić tylko do osób, które ma zapisane na liście kontaktów telefonu, jednak każdy kolega lub koleżanka, do którego lub której zadzwoni, może mu podać listę osób ze swojej listy kontaktów.
Wejście
Pierwszy wiersz wejścia zawiera dwie liczby całkowite n, m (1 <= n, m <=1 000 000) oznaczające, odpowiednio, liczbę osób i liczbę wymian numerów telefonu. W m kolejnych wierszach znajdują się po dwie liczby całkowite a, b (1 <= a, b <= n) oznaczające, że osoby a i b wymieniły się swoimi numerami telefonów. Kolejny wiersz zawiera liczbę całkowitą z (1 ¬ z ¬ 1 000 000) oznaczającą liczbę pytań nauczycielki. W z kolejnych wierszach są po dwie liczby całkowite x, y (1 <= x, y <= n) oznaczające pytanie: czy osoba x jest w stanie przekazać informację osobie y.
Wyjście
Wyjście powinno zawierać z wierszy będących odpowiedziami na kolejne pytania. W każdym wierszu powinno znaleźć się słowo TAK, jeśli osoba mogła przekazać informację, lub NIE, w przeciwnym przypadku.
No i mam takie rozwiązanie z użyciem bfs:

#include "bits/stdc++.h"                                                        
using namespace std;                                                                                                                                       

bool bfs(int node, int key, vector<vector<int>> grafy){                         
    vector<bool> odwiedzone(grafy.size(), false);                                
    vector<int> kolejka;                                                              
    kolejka.push_back(node);                                                          
    odwiedzone[node] = true;                                                 
    if (node == key)                                                            
        return true;                                                            
    for (int i = 0; i < kolejka.size(); i++){                                         
        for (int graf: grafy[kolejka[i]]){                                            
            if (odwiedzone[graf] == false){                                     
                if (graf == key)                                                
                    return true;                                                
                kolejka.push_back(graf);                                              
                odwiedzone[graf] = true;                                        
            }                                                                   
        }                                                                       
    }                                                                           
    return false;                                                               
}                                                                               

int main()                                                                      
{                                                                               
    ios_base::sync_with_stdio(0);                                               
    int n, m, a, b, node, key, z;                                               
    cin >> n >> m;                                                              
    vector<vector<int>> grafy(n+1);                                             
    for (int i = 0; i < m; i++){                                                
        cin >> a >> b;                                                          
        grafy[a].push_back(b);                                                  
        grafy[b].push_back(a);                                                  
    }                                                                           
    cin >> z;                                                                   
    for (int i = 0; i < z; i++){                                                
        cin >> node >> key;                                                     
        if (bfs(node, key, grafy))                                              
            cout << "TAK" << endl;                                              
        else                                                                    
            cout << "NIE" << endl;                                              
    }                                                                           
return 0;                                                                       
} 

niestety przekraczam limit czasu(10 s) o 0.05, jak mógłbym zoptymalizować ten kod?
Tutaj testuje rozwiązania, Nazwa zadania to Lista kontaktow

vector<vector<bool>> graph(n+1,vector<bool>(n+1)); // od razu pełna rezerwacja pamięci, no i wystarczy bool

Od razu użyj algorytmu https://pl.wikipedia.org/wiki/Algorytm_Floyda-Warshalla
Więc masz połączenie każdy z każdym.
for(int a,b;(z--)&&(cin>>a>>b);) cout<<(graph[a][b]?"TAK":"NIE")<<endl;

zastąp wszystkie endl za pomocą '\n'.
dodaj cin.tie(nullptr); na początku.

Spróbowałem tak:

#include "bits/stdc++.h"
using namespace std;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);
    int n, m, z, x, y;
    cin >> n >> m;
    vector<vector<bool>> graph(n+1,vector<bool>(n+1));
    for (int i = 0; i < m; i++){
        cin >> a >> b;
        graph[a][b] = graph[b][a] = true;
    }

    for (int k = 1; k <= n; k++){
        for (int j = 1; j <= n; j++){
            for (int i = 1; i <= n; i++){                                              //algorytm Floyd-Warshall
                graph[i][j] = graph[i][j] || (graph[i][k] && graph[k][j]);
            }
        }
    }
    cin >> z;
    for(int a,b;(z--)&&(cin>>a>>b);) cout<<(graph[a][b]?"TAK":"NIE")<<endl;
return 0;
}

jednak nie przechodzi wszystkich testów, gdzie robię błąd?

Algorytm Floyda-Warshalla ma złożoność O(V^3), czyli dużo za dużo. Do rozwiązania problemu wystarczy znaleźć spójne składowe dla grafu nieskierowanego (w czasie liniowym). Moje przykładowe rozwiązanie:

#!/usr/bin/env python3
from typing import List

n = int(input())
m = int(input())
edges = [[] for _ in range(n)]  # type: List[List[int]]
next_color = 0
no_color = -1
colors = [no_color for _ in range(n)]  # type: List[int]

for _ in range(m):
    a = int(input())
    b = int(input())
    edges[a].append(b)
    edges[b].append(a)


# DFS
def color_graph_component(start_node, current_color):
    assert colors[start_node] == no_color
    queue = edges[start_node].copy()
    while queue:
        node = queue.pop()
        if colors[node] == no_color:
            colors[node] = current_color
            queue.extend(edges[node])
        else:
            assert colors[node] == current_color


z = int(input())
for _ in range(z):
    x = int(input())
    y = int(input())
    if colors[x] == no_color and colors[y] == no_color:
        color_graph_component(x, next_color)
        next_color += 1
    if colors[x] == colors[y]:
        print("TAK")
    else:
        print("NIE")

Kompletnie nieprzetestowane, bo nikt nie podał danych testowych, a mi się nie chce przygotowywać.

Zbuduj strukturę zbiorów rozłącznych z path splitingiem. Ref: https://en.wikipedia.org/wiki/Disjoint-set_data_structure

Budowa Find-Union: O(|E| * log*(|V|) )
Odpytanie czy 2 węzły są połączone: O(log*(|V|))

gdzie log* to logarytm iterowany: https://en.wikipedia.org/wiki/Iterated_logarithm

Szybciej chyba już się nie da.

Edit: @Wibowit wyżej podał szybszy sposób. Moje rozwiązanie sprawdziłoby się, jakbyś musiał dynamicznie dodawać nowe połączenia.