#include <iostream> #include <string> #include <map> #include <stack> #include <vector> using namespace std; map<string, string> represent; map<pair<string, string>, string> ans; pair<string, string> a[100005]; string find_represent(string x){ if (x == represent[x]) return x; else{ represent[x] = find_represent(represent[x]); return represent[x]; } } void unionset(string x, string y){ represent[find_represent(x)] = find_represent(y); } template <class T> class Node{ /* * This is a Tree Node class. */ public: T field, parent; vector<T> son; vector<T> query; string color; Node(T myfield){ field = myfield; son.clear(); query.clear(); parent = ""; color = "white"; } void add_query(T query_name){ query.push_back(query_name); } void add_child(T child){ son.push_back(child); } void set_parent(T sparent){ parent = sparent; } }; template <class T> class GenTree{ public: Node<T> *root; map<T, Node<T>* > nodes; GenTree(){} GenTree(T root_field){ root = new Node<T>(root_field); root->parent = root_field; nodes.insert(pair<T, Node<T>* >(root_field, root)); } Node<T>* add_node(T field, T parent = ""){ Node<T> *node = new Node<T>(field); nodes[field] = node; if (parent!= ""){ nodes[parent]->add_child(field); node->parent = parent; } else node->parent = field; return node; } void add_query(T field, T query_name){ nodes[field]->add_query(query_name); nodes[query_name]->add_query(field); } void traverse(T field){ stack<T> mystack; T temp_field; mystack.push(field); while (!mystack.empty()){ temp_field = mystack.top(); mystack.pop(); cout<<temp_field<<endl; if (nodes[temp_field]->son.size() != 0){ int size = nodes[temp_field]->son.size(); for (int i=size-1; i>=0; i--) mystack.push(nodes[temp_field]->son[i]); } cout<<temp_field<<endl; } } void dfs(T field){ int n = nodes[field]->son.size(); int size = nodes[field]->query.size(); string query_name, color, temp_name1, temp_name2; nodes[field]->color = "grey"; if (size != 0){ for (int i=0; i<size; i++){ temp_name1 = nodes[field]->query[i]; color = nodes[temp_name1]->color; if (color == "grey"){ ans[pair<string, string>(field, temp_name1)] = temp_name1; ans[pair<string, string>(temp_name1, field)] = temp_name1; } else if (color == "black"){ temp_name2 = find_represent(temp_name1); ans[pair<string, string>(field, temp_name1)] = temp_name2; ans[pair<string, string>(temp_name1, field)] = temp_name2; } } } if (n != 0){ for (int i=0; i<n; i++) { T cur_son = nodes[field]->son[i]; dfs(cur_son); } //cout<<field<<" "<<nodes[field]->color<<endl; nodes[field]->color = "black"; unionset(field, nodes[field]->parent); } else{ //cout<<field<<" "<<nodes[field]->color<<endl; nodes[field]->color = "black"; unionset(field, nodes[field]->parent); } } }; int main() { GenTree<string> mytree; int n, m; string name1, name2, root; cin>>n; for (int i=0; i<n; i++){ cin>>name1>>name2; represent[name1] = name1; represent[name2] = name2; if (i==0){ root = name1; mytree.add_node(name1); mytree.add_node(name2, name1); } else mytree.add_node(name2, name1); } cin>>m; for (int i=0; i<m; i++){ cin>>name1>>name2; mytree.add_query(name1, name2); a[i] = pair<string, string>(name1, name2); } mytree.dfs(root); for (int i=0; i<m; i++){ cout<<ans[a[i]]<<endl; } return 0; }
最后一个点过不去。。。
相关推荐
Tree_LCA---倍增
第4章 倍增求LCA-2019-12-05 第4章 倍增求LCA-2019-12-05 第4章 倍增求LCA-2019-12-05
这是一个非常有用的程序主要是用来光谱降维处理的手段有PCA-LCA-LLE-Isomap等.zip
资源分类:Python库 所属语言:Python 资源全名:rmnd-lca-0.1.6.tar.gz 资源来源:官方 安装方法:https://lanzao.blog.csdn.net/article/details/101784059
Prentice.Hall.Embedded.Linux.Systems.with.the.Yocto.Project
无标题ISO17387-LCA法规
COSEL-科索 LCA50S-3 模块电源说明书pdf,COSEL-科索 LCA50S-3 模块电源说明书
LCA词汇复杂度分析软件 跟官网一毛一样 可以做成本地接口
改产品是一款测量水平的仪器,是一款军工产品
API-LCA-乔纳森·林奇
图论--LCA--树上倍增法(在线) 图论--LCA--在线RMQ ST 最小环: 图论--最小环--Floyd模板 树的直径: 图论--树的直径--DFS+树形DP模板 树的重心: 图论--树的重心(DFS) 模板 生成树: ...
lca_app-qvclean-release.apk-1-1663482275650.apk
LCA_树上差分讲解PPT 详细易懂 !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!...
lca_PE-V10.1.2-9015001.apk-1-1694594273570.bin
lca_futureve-app-market(zhihuwap)-release-9.1.0(15618)-armeabi-v7a-bangcle.apk-1-1682906954841.bin
lca_futureve-app-minor-release-8.41.0(13509)-armeabi-v7a-arm64-v8a-bangcle.apk-1-1668495200177.bin
日立LCA电气图纸(K3500490).pdf
LCA 详解以及完整代码详细介绍了倍增法的原理以及Pascal的完整代码 很好很强大
lca_autojspro-latest.apk-1-1669699528859.apk
如“重新审阅LCA问题”中所述,这将使用“范围最小查询”实现LCA。 已完成:天真RMQ,更快RMQ(使用nlogn稀疏表) 待办事项:执行±1 RMQ 天真的RMQ输出: (1(2(4..)(5..))(3(6..)(7..))) indexs : 0, 1, 2, 3,...