In the following discussion, we denote the vertex \((i, j)\) in \(G\) simply as \((i, j)\).

Partial Points Solution

The number of edges can grow to \(\Theta(N^3)\), making it infeasible to connect edges naively. Therefore, we use the concept of supervertices.

For \(j = 2, 3, \ldots, N - 1\), define the sets \(L_0\) and \(R_0\) as \(L_0 \coloneqq \{i \mid A_i = 0, i < j\}\) and \(R_0 \coloneqq \{k \mid A_k = 0, j < k\}\).

Let us consider the case where \(A_j = 1\). For any \(i \in L_0\) and \(k \in R_0\), an edge is added between \((i, j)\) and \((j, k)\). Hence, when \(L_0 \neq \emptyset\) and \(R_0 \neq \emptyset\), all vertices in \(\{(i, j) \mid i \in L_0\} \cup \{(j, k) \mid k \in R_0\}\) belong to the same connected component in \(G\). Based on this, if \(L_0 \neq \emptyset\) and \(R_0 \neq \emptyset\), the way edges are added can be modified as follows without changing the number of connected components:

• Introduce a supervertex \(S_{1,j}\), and connect \(S_{1,j}\) to \((i, j)\) for any \(i \in L_0\), and also connect \(S_{1,j}\) to \((j, k)\) for any \(k \in R_0\).

For the case where \(A_j = 0\), we can similarly reduce the number of edges to \(O(N^2)\) by using supervertices. Refer to the implementation example for details.

From the above, this problem can be solved in \(O(N^2)\) or \(O(N^2 \alpha(N))\) time complexity.

Implementation Example (C++)

Full Points Solution

We divide the problem into isolated vertices and connected components.

Number of Isolated Vertices

A pair \((l, r)\) is an isolated vertex if and only if one of the following conditions is satisfied:

• \(A_l=1, A_r=1\)
• \(A_1=A_2=\cdots=A_l=1, A_r=0, A_{r+1}=A_{r+2}=\cdots=A_N=1\)
• \(A_1=A_2=\cdots=A_{l-1}=1, A_l=0, A_r=A_{r+1}=\cdots=A_N=1\)
• \(A_1=A_2=\cdots=A_l=A_r=A_{r+1}=\cdots=A_N=0\)

Using these properties, the number of isolated vertices can be calculated in \(O(N)\) time.

Number of Connected Components Excluding Isolated Vertices

For \(1 \leq j \leq N\) and \(x, y \in \{0, 1\}\), define a set of vertices \((x, j, y)\) of the graph \(G\) as follows. All vertices in \((x, j, y)\) belong to the same connected component in \(G\).

\[ (x, j, y) \coloneqq \begin{cases} \{(i, j) \mid i < j, A_i = x\} \cup \{(j, k) \mid k > j, A_k = y\} & (\exist i < j, \exist k > j, \text{s.t. } A_i = x, A_k = y, x + A_j + y = 1) \\ \emptyset & (\text{otherwise}) \end{cases} \]

The number of connected components excluding isolated vertices is equal to the number of connected components in the following graph (denoted as \(G^{\prime}\)):

• The vertex set consists of \(\{(x, j, y) \mid 1 \leq j \leq N, x, y \in \{0, 1\}, (x, j, y) \neq \emptyset\}\).
• There is an edge between \((x, j, y)\) and \((z, k, w)\) if and only if \((x, j, y) \neq (z, k, w)\) and \((x, j, y) \cap (z, k, w) \neq \emptyset\).

Proof

Let the number of connected components of \(G^{\prime}\) be \(\alpha\), and denote these connected components by \(G^{\prime}_1, \cdots, G^{\prime}_{\alpha}\). Also, let the vertex set of \(G^{\prime}_t\) be \(V^{\prime}_t\), and define \(U^{\prime}_t\) as the union of all elements in \(V^{\prime}_t\).

Here, we aim to show that \(U^{\prime}_1, \cdots, U^{\prime}_{\alpha}\) are the distinct vertex sets of connected components of \(G\) that are not isolated vertices, and that no other connected components (besides isolated vertices) exist.

To prove this, we need to establish the following four statements:

1. For any vertex \(v\) in \(G\) that is not an isolated point, there exists some \(t\) \((1 \leq t \leq \alpha)\) such that \(v \in U^{\prime}_t\).
2. For any \(s, t\) \((1 \leq s < t \leq \alpha)\), \(U^{\prime}_s \cap U^{\prime}_t = \emptyset\).
3. For any \(t\) \((1 \leq t \leq \alpha)\), all elements of \(U^{\prime}_t\) belong to the same connected component of \(G\).
4. For any distinct vertices \(u, v\) in \(G\) that belong to the same connected component of \(G\), there exists some \(t\) \((1 \leq t \leq \alpha)\) such that \(u, v \in U^{\prime}_t\).

(Proof of 1) For any vertex \(v\) in \(G\) that is not an isolated point, there exists a vertex \((x, j, y)\) in \(G^{\prime}\) such that \(v \in (x, j, y)\). The set \(V^{\prime}_t\) containing \((x, j, y)\) exists uniquely, and for this \(t\), \(v \in U^{\prime}_t\) holds.

(Proof of 2) Assume \(U^{\prime}_s \cap U^{\prime}_t \neq \emptyset\). Then, there exists some vertex \(v\) in \(G\) such that \(v \in U^{\prime}_s\) and \(v \in U^{\prime}_t\). Hence, there exist vertices \((x, j, y)\) and \((z, k, w)\) in \(G^{\prime}\) such that \(v \in (x, j, y)\), \((x, j, y) \in V^{\prime}_s\), \(v \in (z, k, w)\), and \((z, k, w) \in V^{\prime}_t\). Since \(G^{\prime}_s\) and \(G^{\prime}_t\) are distinct connected components of \(G^{\prime}\), it follows that \((x, j, y) \neq (z, k, w)\). However, \((x, j, y)\) and \((z, k, w)\) both contain \(v\), so their intersection is nonempty. Thus, an edge exists between \((x, j, y)\) and \((z, k, w)\) in \(G^{\prime}\), contradicting the assumption that \(G^{\prime}_s\) and \(G^{\prime}_t\) are distinct connected components.

(Proof of 3) For any vertices \((x, j, y)\) and \((z, k, w)\) in \(G^{\prime}\) such that \((x, j, y) \cap (z, k, w) \neq \emptyset\), the union \((x, j, y) \cup (z, k, w)\) belongs to the same connected component of \(G\). Since \(U^{\prime}_t\) is the union of vertices in \(V^{\prime}_t\), all elements of \(U^{\prime}_t\) belong to the same connected component of \(G\) for any \(t\) \((1 \leq t \leq \alpha)\).

(Proof of 4) Assume there exist \(s, t\) \((s \neq t)\) such that \(u \in U^{\prime}_s\) and \(v \in U^{\prime}_t\). Since \(u\) and \(v\) belong to the same connected component of \(G\), all elements of \(U^{\prime}_s \cup U^{\prime}_t\) belong to the same connected component of \(G\). However, since \(U^{\prime}_s \cap U^{\prime}_t = \emptyset\), there exist distinct vertices \(u^{\prime} \in U^{\prime}_s\) and \(v^{\prime} \in U^{\prime}_t\) such that \(u^{\prime}\) and \(v^{\prime}\) are adjacent in \(G\). This implies that there exists a vertex \((x, j, y)\) in \(G^{\prime}\) such that \(u^{\prime} \in (x, j, y)\) and \(v^{\prime} \in (x, j, y)\). The vertex \((x, j, y)\) must belong to either \(G^{\prime}_s\) or \(G^{\prime}_t\), leading to \(u^{\prime}, v^{\prime} \in U^{\prime}_s\) or \(u^{\prime}, v^{\prime} \in U^{\prime}_t\), which contradicts \(U^{\prime}_s \cap U^{\prime}_t = \emptyset\).

Thus, the number of connected components of \(G\) that are not isolated vertices is \(\alpha\), which equals the number of connected components of \(G^{\prime}\). (End of Proof)

Two distinct vertices \((x, j, y)\) and \((z, k, w)\) \((j \leq k)\) in \(G^{\prime}\) have a non-empty intersection if and only if the following condition is satisfied:

• \(j < k\) and \(A_j = z, A_k = y\)

Using this property, we can construct edges in \(G^{\prime}\) without changing the number of connected components as follows:

• For \((x, y) = (0, 0), (0, 1), (1, 0)\):
  • Let \(m\) and \(M\) be the minimum and maximum indices \(j\) satisfying \(A_j = 1 - x - y\) and \((x, j, y) \neq \emptyset\) (if no such \(j\) exists, let \(m = N + 1, M = 0\)). For \(k = m + 1, \cdots, N\), if \(A_k = y\) and \((1 - x - y, k, x) \neq \emptyset\), add an edge between \((x, m, y)\) and \((1 - x - y, k, x)\). Similarly, for \(k = 1, \cdots, M - 1\), if \(A_k = x\) and \((y, k, 1 - x - y) \neq \emptyset\), add an edge between \((x, M, y)\) and \((y, k, 1 - x - y)\).

Using this approach to manage \(G^{\prime}\), the number of connected components excluding isolated vertices can be determined in \(O(N)\) time.

Thus, the problem can be solved in \(O(N)\) per test case. Using Union-Find for component management results in \(O(N \alpha(N))\), which is also efficient.

Implementation Example (C++)