hiho_1067_最近公共祖先2

￡神魔★判官ぃ 2022-03-27 04:43 205阅读 0赞

##### **题目大意** #####

给出一棵家谱树，树中的节点都有一个名字，保证每个名字都是唯一的，然后进行若干次查询，找出两个名字的最近公共祖先。  
题目链接[最近公共祖先][Link 1]

#### **分析** ####

数据量大，根据题目提示，采用Tarjan + 并查集算法，进行离线LCA查询操作。即先将所有的查询存储下来，然后统一DFS遍历一遍家族树，在遍历的过程中对遍历到的当前节点相关的那些查询进行设置答案。遍历完整棵树之后，再输出答案。  
从根节点开始遍历，对树中的每个节点都设置一个颜色（白色表示未被访问，灰色表示DFS过程中进入到该节点所在的子树，还是没有从该节点所在的子树离开；黑色表示离开该节点所在的子树）。对当前正在访问的节点，则可以对和该节点相关的那些查询进行回复（只是得到答案，并存储下来，遍历完整个树后统一回复）：  
记当前节点为node1， 如果某个查询需要得到node1和node2的LCA，判断node2的颜色，  
如果为白色，表示node2还没有被访问过，则此次先不用回复，等到node2被访问到的时候，再进行回复（那时候 node1的颜色和node2的颜色均不为白色）；  
如果为灰色，表示node2在node1先前被经过，且还没有结束，画图可知，node2就是node1和node2的LCA。  
如果为黑色，那么需要从node2向上查找一个最低的灰色节点，且该节点就在node1到根节点的路径上。那个灰色节点就是node1和node2的LCA。为了加快node2上方的最低灰色节点的查找，使用并查集：  
一个节点的子节点node的初始root为子节点本身，当子节点在被访问完（颜色被设置为黑色）之后，将子节点的root设置为node。那么，一个黑色节点的root就是它上方最低的那个灰色节点！

做题中间犯了一些错误：  
没有考虑到可能多个查询的内容相同；开始做的时候，存储了每个节点相关的查询的节点unordered\_map> ，想着这样在Tarjan遍历到该节点的时候，直接从vector中找到该节点相关的查询的节点。  
然后对于每个查询对 person1，person2，映射到一个key(person1.id \* MAX + person2.id)， 然后对应到一个value（即查询的序号），想着这样在进行Tarjan遍历到节点时候，通过节点person1，找到它相关的各个person2，然后找到key，再找到查询的序号 num，将查到的结果放到 resultt\[num\]中。  
这样想法挺好啊，可是如果多个查询的内容相同，则歇菜了。。。修改的方法是，对于每个查询对，维护一个vector，存放和它相关的各个查询的序号。改动比较麻烦，就换了另外一种存储方法。

#include<iostream>
    #include<string.h>
    #include<iostream>
    #include<queue>
    #include<unordered_map>
    #include<unordered_set>
    #include<string>
    #include<vector>
    using namespace std;
    unordered_map<string, int> gName2node;
    unordered_map<int, string> gNode2name;
    unordered_map<int, vector<int>> gNodeQueryIds; //对应每个节点，它所相关的查询的id
    vector<pair<int, int>> gQueries;	//查询，表示查询的两个人的id
    vector<string> gQueryResult;
    const int kMax = 200005;
    int gRoot[kMax];
    
    struct Edge{
    	int to;
    	int next;
    };
    Edge gEdges[kMax];
    int gEdgeIndex;
    int gHead[kMax];
    int gNodeColor[kMax];
    
    void InsertEdge(int u, int v){
    	int e = gEdgeIndex++;
    	gEdges[e].to = v;
    	gEdges[e].next = gHead[u];
    	gHead[u] = e;
    }
    int GetRoot(int a){
    	if (gRoot[a] == a)
    		return a;
    	return gRoot[a] = GetRoot(gRoot[a]);
    }
    
    void Union(int a, int b){
    	int p1 = GetRoot(a);
    	int p2 = GetRoot(b);
    	gRoot[p2] = p1;
    }
    
    void AddPerson(string person){
    	if (gName2node.find(person) == gName2node.end()){
    		int node = gName2node.size();
    		gName2node[person] = node;
    		gNode2name[node] = person;
    	}
    }
    void Init(int n){
    	gEdgeIndex = 0;
    	memset(gEdges, -1, sizeof(gEdges));
    	memset(gHead, -1, sizeof(gHead));
    	memset(gNodeColor, 0, sizeof(gNodeColor));
    	for (int i = 0; i <= 2*n; i++){
    		gRoot[i] = i;
    	}
    }
    void Tarjan(int node){
    	gNodeColor[node] = 1;
    
    	for (int e = gHead[node]; e != -1; e = gEdges[e].next){
    		int v = gEdges[e].to;
    		Tarjan(v);
    		gRoot[v] = node;
    	}
    
    	if (! gNodeQueryIds[node].empty()){
    		for (auto it = gNodeQueryIds[node].begin(); it != gNodeQueryIds[node].end(); ++it){
    			int query_id = *it;
    			int node2;
    			if (node == gQueries[query_id].first)
    				node2 = gQueries[query_id].second;
    			else
    				node2 = gQueries[query_id].first;
    			if (gNodeColor[node2] == 0) //还没有被访问过
    				continue;
    			if (gNodeColor[node2] == 1){ 
    				//节点node2在节点node之前被访问，且访问未结束，则可以确定node2在node到根节点的路径上
    				gQueryResult.at(query_id) = gNode2name[node2];
    				//cout << "assign, = " << gQueryResult.at(gQueryResultIndex[node*kMax + node2]) << endl;
    			}
    			else{//节点node2已经被访问过，且访问结束,那么node2节点所在集合的根节点（并查集的根）就是最低公共祖先
    				int lca = GetRoot(node2);
    				gQueryResult.at(query_id) = gNode2name[lca];
    			}
    		}
    	}
    
    
    
    	gNodeColor[node] = 2;
    }
    int main(){
    	int n, n1, n2;
    	string person1, person2;
    	cin >> n;
    	Init(n);
    	for (int i = 0; i < n; i++){
    		cin >> person1 >> person2;
    		AddPerson(person1);
    		AddPerson(person2);
    		n1 = gName2node[person1];
    		n2 = gName2node[person2];
    		InsertEdge(n1, n2);
    	}
    	int m;
    	cin >> m;
    	gQueryResult.assign(m, "");
    	for (int i = 0; i < m; i++){
    		cin >> person1 >> person2;
    		n1 = gName2node[person1];
    		n2 = gName2node[person2];
    		gQueries.push_back(pair<int, int>(n1, n2));
    		gNodeQueryIds[n1].push_back(i);
    		gNodeQueryIds[n2].push_back(i);
    	}
    	Tarjan(0);
    	for (int i = 0; i < m; i++){
    		cout << gQueryResult[i] << endl;
    	}
    	return 0;
    }

[Link 1]: http://hihocoder.com/problemset/problem/1067

发表评论取消回复

表情：

评论列表（有 0 条评论，205人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode236.最近的公共祖先

![在这里插入图片描述][fcc7f7a044d24cf892746081a0dc16ac.png] 求解最近公共祖先的算法分为两个步骤： 1. 求出两节点路径

电玩女神/ 2023年09月25日 21:27/ 0 赞/ 54 阅读

相关 lintcode88. 最近公共祖先

给定一棵二叉树，找到两个节点的最近公共父节点(LCA)。最近公共祖先是两个节点的公共的祖先节点且具有最大深度。样例样例 1: 输入

￡神魔★判官ぃ/ 2023年07月03日 10:40/ 0 赞/ 21 阅读

相关最近公共祖先LCA

最近公共祖先（Lowest Common Ancestors，LCA）指有根树中距离两个节点最近的公共祖先。祖先指从当前节点到树根路径上的所有节点。 ![2021042810

蔚落/ 2023年01月17日 08:29/ 0 赞/ 137 阅读

相关 leetcode---236. 二叉树的最近公共祖先(最近公共祖先)

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是

矫情吗；*/ 2022年11月28日 00:42/ 0 赞/ 197 阅读

相关 leetcode---235. 二叉搜索树的最近公共祖先（最近公共祖先）

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x

女爷i/ 2022年11月28日 00:42/ 0 赞/ 195 阅读

相关 LCA 最近公共祖先

[https://www.cnblogs.com/JVxie/p/4854719.html][https_www.cnblogs.com_JVxie_p_4854719.htm

Myth丶恋晨/ 2022年06月02日 11:37/ 0 赞/ 177 阅读

相关最近公共祖先

对于有根树上的两个节点u, v，最近公共祖先`lca(u, v) = x`，x是u, v的祖先并且深度尽可能大 ![一棵树][1240] 对于这棵树来说`lca(9, 1

喜欢ヅ旅行/ 2022年05月13日 07:56/ 0 赞/ 250 阅读

相关 hiho_1067_最近公共祖先2

题目大意给出一棵家谱树，树中的节点都有一个名字，保证每个名字都是唯一的，然后进行若干次查询，找出两个名字的最近公共祖先。题目链接[最近公共祖先][Link 1]

￡神魔★判官ぃ/ 2022年03月27日 04:43/ 0 赞/ 206 阅读

相关【牛客网】最近公共祖先

题目描述有一棵无穷大的满二叉树，其结点按根结点一层一层地从左往右依次编号，根结点编号为1。现在有两个结点 a，b。请设计一个算法，求出a和b点的最近公共祖先的编号。

青旅半醒/ 2022年01月23日 05:59/ 0 赞/ 226 阅读

相关 LCA最近公共祖先-- HDU 2586

[题目链接][Link 1] Problem Description There are n houses in the village and some bidir

「爱情、让人受尽委屈。」/ 2021年12月01日 17:34/ 0 赞/ 259 阅读