模板
1. Tarjan
一个讲的很好的视频:D10 Tarjan算法 P3379【模板】最近公共祖先(LCA)_哔哩哔哩_bilibili,董晓算法出品。
Tarjan总体来说可以概括为:
- 记录访达:记录某个节点是否已经访问过,防环
- 向下深搜:深搜子节点
- 回溯指父:低层回溯时将子节点归于当前父节点所在等价类中
- 离时查询:本层向上回溯时查询与当前节点所有相关的LCA,记录答案
package Tarjan.LCA;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class TarjanLCA {
private List<Integer>[] e;
private List<int[]>[] query;
private int[] fa;
private boolean[] vis;
private int[] ans;
/**
* 求LCA
* @param edge 边集
* @param queries 查询
* @param n 总共几个节点
* @return 查询对应的LCA集合
*/
public int[] Tarjan(int[][] edge,int[][] queries,int n,int root){
e = new ArrayList[n];
Arrays.setAll(e,e->new ArrayList<>());
query = new ArrayList[n];
Arrays.setAll(query,e->new ArrayList<>());
fa = new int[n];
for (int i = 0; i < fa.length; i++) {
fa[i] = i;
}
vis = new boolean[n];
Arrays.fill(vis,false);
ans = new int[queries.length];
// 邻接表建边
for (int[] es : edge) {
e[es[0]].add(es[1]);
e[es[1]].add(es[0]);
}
// tarjan 查询数组
for (int i = 0; i < queries.length; i++) {
int[] qs = queries[i];
query[qs[0]].add(new int[]{qs[1],i});
query[qs[1]].add(new int[]{qs[0],i});
}
dfs(root);
return ans;
}
private void dfs(int node){
vis[node] = true;
for (Integer child : e[node]) {
if(!vis[child]){
dfs(child);
fa[child] = node;
}
}
// 向上一层返回时记录LCA
for (int[] q : query[node]) {
if(vis[q[0]]){
ans[q[1]] = find(q[0]);
}
}
}
private int find(int x){
if(fa[x]!=x){
fa[x] = find(fa[fa[x]]);
}
return fa[x];
}
}
这里有几个要注意的地方:
- 查询数组记得要对称设置,比如查3,4的lca,3要放1个,4也要放1个。因为到底哪个先深搜到是不确定的。比如就放了3的,那如果先深搜到3,发现此时4压根就没指父过(压根没访问到),这个查询对应的答案就没法记录了。所以都放一个绝对可以防止深搜顺序的不确定性。
- 并查集的路径压缩并不会影响查询结果。因为是回溯时查询,所以绝对是从低层起的,随着逐渐往根处的回溯,并查集中等价类会逐渐向根扩张,并以根为祖宗节点。
这里放一个例子,可以对照代码手玩一下:
0
/
4 3
/|
1 5 6 8
/
2 7
测试用例可自选。
1. LC 2846 边权重均等查询
树的定义是连通无回路的图,所以会有以下性质:
- 任意两个节点间有且仅有一条通路
- 任意节点至多有一个父节点
所以要查询任意两个节点之间的最小操作次数,可以唯一地确定答案。因为这两个节点之间存在且仅只存在一条通路。
这个贪心其实很显然,就是对于一条链,让其他权重向频率最大的那个靠近即可。比如这条链上的权重为:
[ 1 , 1 , 2 , 2 , 2 , 3 ]
很显然答案是把1和3全部变成2,操作次数是3。
那么怎么计算这条链上的操作次数呢?这里定义i→j为从节点i到节点j上的链上各权重出现频次。计算公式为:
op(i->j) = ∑(op(0->i) + op(0->j) - 2*op(0->lca(i,j)))
其中lca表示最近公共祖先
举个例子:
0
/
4 3
/|
1 5 6 8
/
2 7
- 假设我们要看6→7这条链,那么可以计算 0→6 + 0→7 – 0→4 – 0→4的各权重出现频次。因为0→4多算了两次那么这个公式是否具有普适性呢?
- 假设现在要看4→3这条链,可以计算0→4+0→3 – 2* 0→0,也是适用的。
所以思路就是,我们先通过深搜,求出来每个节点到根节点(一颗无向树,谁都可以作为根节点,不妨设为0)0的链上各权重出现频次。然后利用tarjan求出来每组查询的公共祖先,带入上述公式计算即可。
深搜求频次的思路是:由于本层递归比上一层就多了一个上一层节点到本层节点的权重,因此我们可以复制上一层节点(本层节点的父节点)的各权重频次,再在当前权重上增1即可。
而利用性质2,可以简单的记录fa节点判环。但tarjan是不能这样做的,因为需要明确离时查询时另一个节点是否已经访问,并不只是简单的判环功能。
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
class Solution {
List<int[]>[] e;
List<int[]>[] qs;
int[][] cnt;
int[] lca;
int[] fa;
boolean[] vis;
int[] ans;
public int[] minOperationsQueries(int n, int[][] edges, int[][] queries) {
e = new ArrayList[n];
qs = new ArrayList[n];
Arrays.setAll(e,e->new ArrayList<>());
Arrays.setAll(qs,e->new ArrayList<>());
int u,v,w;
//邻接表
for (int[] edge : edges) {
u = edge[0];
v = edge[1];
w = edge[2];
e[u].add(new int[]{v,w});
e[v].add(new int[]{u,w});
}
// tarjan 查询
for (int i = 0; i < queries.length; i++) {
int[] q = queries[i];
qs[q[0]].add(new int[]{q[1],i});
qs[q[1]].add(new int[]{q[0],i});
}
cnt = new int[n][26];
cnt_dfs(0,-1,0);
lca = new int[queries.length];
fa = new int[n];
for (int i = 0; i < fa.length; i++) {
fa[i] = i;
}
vis = new boolean[n];
Arrays.fill(vis,false);
tarjan(0);
ans = new int[queries.length];
calAns(queries);
return ans;
}
private void cnt_dfs(int node,int father,int weight){
if(father!=-1){
cnt[node] = Arrays.copyOf(cnt[father],26);
cnt[node][weight-1]++;
}
for (int[] child : e[node]) {
if(child[0]!=father){
cnt_dfs(child[0],node,child[1]);
}
}
}
private void tarjan(int node){
vis[node] = true;
for (int[] child : e[node]) {
if(!vis[child[0]]){
tarjan(child[0]);
// tarjan 回溯指父
fa[child[0]] = node;
}
}
// 离时查询
for (int[] q : qs[node]) {
if(vis[q[0]]){
lca[q[1]] = find(q[0]);
}
}
}
private int find(int x){
if(fa[x]!=x){
fa[x] = find(fa[fa[x]]);
}
return fa[x];
}
private void calAns(int[][] queries){
int sum,max;
for (int index = 0; index < queries.length; index++) {
sum = 0;
max = Integer.MIN_VALUE;
int u = queries[index][0];
int v = queries[index][1];
for(int i=0;i<26;i++){
int freq = cnt[u][i] + cnt[v][i] - 2*cnt[lca[index]][i];
sum += freq;
max = Math.max(freq,max);
}
ans[index] = sum-max;
}
}
}
原文地址:https://blog.csdn.net/lyh20021209/article/details/135872975
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:http://www.7code.cn/show_62805.html
如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱:suwngjj01@126.com进行投诉反馈,一经查实,立即删除!