图论2
1.找父亲节点
int find (int x) {
if(x==fa[x]) return x;
return fa[x]=find(fa[x]);
}
状态压缩+合并后时间复杂度O(n*alpha(n))
alpha:反阿克曼函数
2.最小生成树
Kruskal：
时间复杂度O(m log(m))
关键sort()
Prim:
时间复杂度O((m+n)log(m))
Or 暴力O(n^2+m)
可能比Kruskal更优
关键priority_queue
3.Kruskal重构树
sort()
for(int i=0;i<m;i++){
fait[find(x)] =++tot;
fait[find(y)] tot;
val[tot]=e[i].val;
}
4.P1967
首先重新建图，构造出最大生成树，然后在最大生成树上求LCA来回答询问即可。