tarjan

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

tarjan

主要使用场景场景

LCA问题,多组询问

注意事项

tarjan挺复杂的…代码中使用了一个unordered_map<int, vector<int>> checkIfQuery;数组来检测当前点是否被挂载了询问,但是当要求输出询问组按给定序号时,不能只使用vector<int>,需要把节点的序号信息也存在数组里(做成结构体)

结构

需要基本并查集结构 parent数组findRoot函数union函数 需要一个map来标记该节点是否有询问对需要函数insert把询问对插到map相应点位里需要函数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

参考文献