hihoCoder_#1067_最近公共祖先·二(LCA模板) - c++编程基础

的LCA问题。

代码清单：

#include

#include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; const int maxn = 1e5 + 5; struct Edge{ int v,id; Edge(int v,int id){ this -> v = v; this -> id = id; } }; int n,m,id,root; string name1,name2; bool hasfa[maxn]; map idx; string str[maxn]; vector graph[maxn]; int father[maxn]; int color[maxn],ans[maxn]; vector edge[maxn]; int Find(int x){return x!=father[x] ? father[x]=Find(father[x]) : father[x]; } void init(){ for(int i=0;i >name1>>name2; int idx1=get_idx(name1); int idx2=get_idx(name2); graph[idx1].push_back(idx2); hasfa[idx2]=true; } scanf(%d,&m); for(int i=1;i<=m;i++){ cin>>name1>>name2; int idx1=get_idx(name1); int idx2=get_idx(name2); edge[idx1].push_back(Edge(idx2,i)); edge[idx2].push_back(Edge(idx1,i)); } } void tarjan(int u){ color[u]=1; for(int i=0;i

hihoCoder_#1067_最近公共祖先·二(LCA模板)(二)