考虑倒着处理所有操作，相当于每次可以选择一个颜色，满足所有该颜色的点形成一个连通块，并将这些点的颜色修改为 $-1$。经过若干个颜色为 $-1$ 的点连通也算作连通。

使用并查集合并所有同种颜色 $c$ 能通过颜色 $c$ 和 $-1$ 两种边连通的点。对于每个颜色为 $-1$ 的连通块，要时刻将相邻连通块中颜色相同的合并。只需要对每个这样的连通块维护一个 std::map，连通块被合并时使用启发式合并递归下去即可。

时间复杂度为 $\mathcal{O}(n \log^2 n)$。如果使用哈希表存储那么就是 $\mathcal{O}(n \log n)$。