CF1691E Number of Groups

在数轴上给定 $n$ 个有颜色的线段。每个线段要么是红色，要么是蓝色。第 $i$ 个线段可以用三元组 $(c_i, l_i, r_i)$ 表示，表示该线段包含区间 $[l_i, r_i]$ 上的所有点，颜色由 $c_i$ 指定： - 如果 $c_i = 0$，则为红色线段； - 如果 $c_i = 1$，则为蓝色线段。 我们称两个不同颜色的线段是“相连”的，如果它们至少有一个公共点。若两个线段直接相连，或者通过一系列直接相连的线段间接相连，则它们属于同一组。请你求出线段被分成了多少组。 

每个测试点包含多组测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^5$），表示测试用例的组数。 每组测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 10^5$），表示线段的数量。 接下来的 $n$ 行，每行包含三个整数 $c_i, l_i, r_i$（$0 \leq c_i \leq 1, 0 \leq l_i \leq r_i \leq 10^9$），描述第 $i$ 个线段。 保证所有测试用例中 $n$ 的总和不超过 $10^5$。

对于每组测试用例，输出一个整数 $k$，表示线段被分成的组数。

在第一个样例中，有 $5$ 条线段。第 $1$ 条和第 $2$ 条线段因为颜色不同且有公共点而相连。第 $2$ 条和第 $3$ 条线段也相连，第 $4$ 条和第 $5$ 条线段也相连。因此，总共分成两组：$\{1, 2, 3\}$ 和 $\{4, 5\}$。 由 ChatGPT 4.1 翻译