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

參考文獻