Find connected components in a graph of computer network with parallel pairwise tests

Question

I have N nodes, a node might have an undirected edge to other nodes, resulting in K connected components (K<=N, K unknown).
I can test if a given pair is connected. In each step in time, I can run N/2 such tests in parallel (a given node can be tested once per step). Each connected component is a cluster graph (it has no three-vertex induced path). The goal is to find all K components and list of nodes per component.

The actual application is nodes in a computer network, therefore I can run pairwise tests in parallel. I have ~256 nodes. How to approach this? A naive solution of N*(N-1)/2 tests is too costly. Hopefully I could reuse a library algorithm in Python a solution.

For example for detecting the graph below (7 nodes, 3 connected-components (CC)), I might need this set of tests:

Step1 tests: D-A, C-F, E-B
Step2 tests: A-B, C-B, D-E (found CC: A-B-C)
Step3 tests: D-F (Found CC: D)
Step4 tests: E-F (Found CC: E-F)
Done.

Answer 1

The best you can do is about $N$ steps.

You can do it in about $N$ steps, by just testing $N/2$ new pairs in each step, until you've tested all pairs. Then once you have tested all pairs, you can use any standard algorithm to compute connected components (e.g., depth-first search).

You can't do better. In the worst case, you have to inspect essentially every pair of nodes, so you'll need to have inspected about $N^2/2$ pairs. (If there is even a single pair $u,v$ that you haven't inspected, where there is no other path of length $>1$ from $u$ to $v$, then you can't tell whether $u,v$ are in the same component or not without querying the $u,v$ pair.) Since you can only inspect $N/2$ pairs per step, you'll need at least $N$ steps.