I am starting to learning dynamic connectivity, but I don't know how to get started on the following problem:

Given an int N specifying the total number of sites (indexed 0 through N - 1), the dynamic connectivity problem specifies the following API describing the basic operations that we need.

connect(int p, int q): Add a connection between sites p and q.

isConnected(int p, int q): Returns true if and only if sites p and q are in the same component.

The connect and isConnected operations model an equivalence relation, which means that it is:

Reflexive: p is connected to p.

Symmetric: If p is connected to q, then q is connected to p.

Transitive: If p is connected to q and q is connected to r, then p is connected to r.

We may introduce 2 arrays of size N.

For each of the following conditions, please give a basic and concise English description of a dynamic connectivity algorithm that meets the requirements.

Runtime for connect is in O(1) while isConnected is in O(N).

Runtime for connect is in O(N) while isConnected is in O(1).

Runtime for connect is in O(log N) while isConnected is in O(log N).