道路修建 – 启发式并查集

无向图G初始有n个点,从1到n依次标号,但是没有边,

接下来有m次操作,从1到m依次标号,你需要对每种操作输出相应的结果,操作分为两种:

0_u_v:加入一条连接标号为u和标号为v的点的边,输出加边后图G中连通块的个数。

1_u_v:查询标号为u和标号为v的点之间是否连通,如果连通,输出k,表示最早在第k次操作后标号为u和标号为v的点之间连通,否则输出0。

启发式并查集,在每个节点上维护一个tm[i]表示最后和另外一颗子树合并的时间。查询两个点最早合并时间,在两个的公共祖先路劲上找最大的tm[i]

 

LEAVE A COMMENT