并查集的路径压缩或启发式合并可以把时间复杂度降低到log级别，如果同时采用，可以降低到常数级别，第四题其实可以先写个素数筛法预处理所有数字的质因子，然后dfs染色。