tarjanLCA算法

tarjan

• tarjan
• • 主要使用场景场景
  • 注意事项
  • 结构
  • 模板
  • • 结构模板
    • • 主体
      • 并查集条件
      • 插入询问数组
      • dfs
  • 实现
  • • cpp
• 经典问题
• • • LCA
    • • 问题描述
      • 例题演示
      • 实现
      • • cpp
• 参考文献

tarjan

主要使用场景场景

• LCA问题,多组询问

注意事项

• tarjan挺复杂的…
• 代码中使用了一个

  unordered_map<int, vector<int>> checkIfQuery;

  数组来检测当前点是否被挂载了询问,但是当要求输出询问组按给定序号时,不能只使用

  vector<int>

  ,需要把节点的序号信息也存在数组里(做成结构体)

结构

1. 需要基本并查集结构

• parent数组
• findRoot函数
• union函数

1. 需要一个map来标记该节点是否有询问对
2. 需要函数insert把询问对插到map相应点位里
3. 需要函数dfs对树进行后序的dfs.

模板

结构模板

主体

读入树和询问表

void tarjanLCA(node *tree, vector<query> &qList)
{
    //必须组件.并查集
    vector<int> parent(maxVertex);
    for (int i = 0; i < maxVertex; i++)
    {
        parent[i] = -1;
    }
    unordered_map<int, vector<int>> checkIfQuery; //用来检查当前节点是否是被询问的节点之一.
    vector<bool> known(maxVertex);                //用来标记是否访问过.
    insertQuery(qList, checkIfQuery);
    dfs(tree, qList, parent, known, checkIfQuery);
}
           

并查集条件

这里的联合函数很简单,用的时候记得把子插到父底下就行.

int findRoot(int nodeIndex, vector<int> parent)
{
    while (parent[nodeIndex] != -1)
    {
        nodeIndex = parent[nodeIndex];
    }
    return nodeIndex;
}
void unionNode(int a, int b, vector<int> &parent)
{
    parent[findRoot(b, parent)] = findRoot(a, parent); //把b插到a下面
}
           

插入询问数组

代码中使用了一个

unordered_map<int, vector<int>> checkIfQuery;

数组来检测当前点是否被挂载了询问,但是当要求输出询问组按给定序号时,不能只使用

vector<int>

,需要把节点的序号信息也存在数组里(做成结构体)

void insertQuery(vector<query> qList, unordered_map<int, vector<int>> &checkIfQuery) //把问题插入对应节点.
{
    for (int i = 0; i < qList.size(); i++)
    {
        checkIfQuery[qList[i].x].push_back(qList[i].y);
        checkIfQuery[qList[i].y].push_back(qList[i].x);
    }
}
           

dfs

这个dfs是后序的.

void dfs(node *tree, vector<query> &qList, vector<int> &parent, vector<bool> &known, unordered_map<int, vector<int>> checkIfQuery) //注意是后序
{
    if (tree->l != NULL)
    {
        dfs(tree->l, qList, parent, known, checkIfQuery);
        unionNode(tree->v, tree->l->v, parent);
    }
    if (tree->r != NULL)
    {
        dfs(tree->r, qList, parent, known, checkIfQuery);
        unionNode(tree->v, tree->r->v, parent);
    }
    //后序
    known[tree->v] = true; //标记访问了.

    for (int i = 0; i < checkIfQuery[tree->v].size(); i++)
    {
        if (known[checkIfQuery[tree->v][i]] == true) //访问过
        {
            qList.push_back({tree->v, checkIfQuery[tree->v][i], findRoot(checkIfQuery[tree->v][i], parent)}); //当前的根就是公共祖先
        }
        else
        {
            //没访问过不管.
        }
    }
}
           

实现

cpp

#include <bits/stdc++.h>
#include <vector>
using namespace std;
const int maxVertex = 1000;
typedef struct node //假设1树是这样的.
{
    int v;
    struct node *l = NULL;
    struct node *r = NULL;
} node;
typedef struct query //假设询问是这样的,答案也保存在组里.
{
    int x;
    int y;
    int LCA;
} query;
//首先需要实现并查集.
int findRoot(int nodeIndex, vector<int> parent)
{
    while (parent[nodeIndex] != -1)
    {
        nodeIndex = parent[nodeIndex];
    }
    return nodeIndex;
}
void unionNode(int a, int b, vector<int> &parent)
{
    parent[findRoot(b, parent)] = findRoot(a, parent); //把b插到a下面
}

void insertQuery(vector<query> qList, unordered_map<int, vector<int>> &checkIfQuery) //把问题插入对应节点.
{
    for (int i = 0; i < qList.size(); i++)
    {
        checkIfQuery[qList[i].x].push_back(qList[i].y);
        checkIfQuery[qList[i].y].push_back(qList[i].x);
    }
}
void dfs(node *tree, vector<query> &qList, vector<int> &parent, vector<bool> &known, unordered_map<int, vector<int>> checkIfQuery) //注意是后序
{
    if (tree->l != NULL)
    {
        dfs(tree->l, qList, parent, known, checkIfQuery);
        unionNode(tree->v, tree->l->v, parent);
    }
    if (tree->r != NULL)
    {
        dfs(tree->r, qList, parent, known, checkIfQuery);
        unionNode(tree->v, tree->r->v, parent);
    }
    //后序
    known[tree->v] = true; //标记访问了.

    for (int i = 0; i < checkIfQuery[tree->v].size(); i++)
    {
        if (known[checkIfQuery[tree->v][i]] == true) //访问过
        {
            qList.push_back({tree->v, checkIfQuery[tree->v][i], findRoot(checkIfQuery[tree->v][i], parent)}); //当前的根就是公共祖先
        }
        else
        {
            //没访问过不管.
        }
    }
}
//qList最后在后面那几个是录入的找到的对,找不到的录不进去的.
void tarjanLCA(node *tree, vector<query> &qList)
{
    //必须组件.并查集
    vector<int> parent(maxVertex);
    for (int i = 0; i < maxVertex; i++)
    {
        parent[i] = -1;
    }
    unordered_map<int, vector<int>> checkIfQuery; //用来检查当前节点是否是被询问的节点之一.
    vector<bool> known(maxVertex);                //用来标记是否访问过.
    insertQuery(qList, checkIfQuery);
    dfs(tree, qList, parent, known, checkIfQuery);
}
int main(int argc, char const *argv[])
{

    node *tree = new node; //假设这是树.
    tree->v = 0;
    tree->l = new node;
    tree->l->v = 1;
    tree->r = new node;
    tree->r->v = 2;
    vector<query> qList; //设这是询问的所有问题组.答案也保存在组里.
    qList.push_back({1, 2});
    tarjanLCA(tree, qList);
    return 0;
}

           

经典问题

LCA

问题描述

例题演示

实现

cpp

参考文献