本文共 1281 字，大约阅读时间需要 4 分钟。
先求一个节点的所有先人，然后从另外一个节点开始向上找，找到第一个共同的先人就是最近公共祖先。
#include #include #include #include using namespace std;int fathe[1222];int color[122];int father[1222];int getfather(int x){ if (x != fathe[x]) fathe[x] = getfather(fathe[x]); return fathe[x];}void add(int a, int b){ int fa = getfather(a); int fb = getfather(b); fathe[fa] = fb;}void Find(int x){ while (father[x]!=-1&&father[x]!=x){ color[x] = 1; x = father[x]; } color[x] = 1;}int find1(int x){ while(father[x]!=-1&&father[x]!=x){ if(color[x]) return x; x = father[x] ; } return x;}int main(){ int n; string a,b; //memset(color,0,sizeof(color)); memset(father,-1,sizeof(father)); map m; map m1; cin >> n; int sum = 1; for(int i =1;i<=1000;i++) fathe[i] = i; for (int i = 0; i < n; i++){ cin >> a >> b; int c; int d; if (!m.count(a)) m[a] = sum, m1[sum] = a,sum++; if (!m.count(b)) m[b] = sum, m1[sum] = b,sum++; c = m[a]; d = m[b]; father[d] = c; add(d, c); } int q; cin >> q; for (int i = 0; i < q; i++){ memset(color,0,sizeof(color)); cin >> a >> b; if(!m.count(a)||!m.count(b)){ if(a==b) cout< <
转载于:https://www.cnblogs.com/yigexigua/p/4072673.html