朴素算法：洛谷70分,O2 80分
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 | #include<iostream> #include<vector> using namespace std; int n, m, s; vector<int> edges[500005]; int father[500005],depth[500005]; void dfs(int node, int fath) { father[node] = fath; depth[node] = depth[fath] + 1; for (int i = 0; i < edges[node].size(); i++) { if (edges[node][i] == fath)continue; dfs(edges[node][i], node); } } int query(int a, int b) { while (a != b) { if (depth[a] >= depth[b])a = father[a]; else b = father[b]; } return a; } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> m >> s; for (int i = 1; i <= n - 1; i++) { int x, y; cin >> x >> y; edges[x].push_back(y); edges[y].push_back(x); } dfs(s, s); for (int i = 1; i <= m; i++) { int a, b; cin >> a >> b; cout << query(a, b) << "\n"; } } |
倍增：洛谷80分，O2 100分
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 | #include<iostream> #include<vector> #include<algorithm> #define MAXLOG 20 using namespace std; int n, m, s; vector<int> edges[500005]; int depth[500005]; int ancestor[500005][MAXLOG+2]; void dfs(int node, int fath) { ancestor[node][0] = fath; depth[node] = depth[fath] + 1; for (int i = 1; i <= MAXLOG; i++)ancestor[node][i] = ancestor[ancestor[node][i - 1]][i - 1]; for (int i = 0; i < edges[node].size(); i++) { if (edges[node][i] == fath)continue; dfs(edges[node][i], node); } } int query(int a, int b) { if (depth[b] > depth[a])swap(a, b); for (int i = MAXLOG; ~i; i--)if (depth[ancestor[a][i]] >= depth[b])a = ancestor[a][i]; if (a == b)return a; for (int i = MAXLOG; ~i; i--) if(ancestor[a][i]!=ancestor[b][i]){ a = ancestor[a][i]; b = ancestor[b][i]; } return ancestor[a][0]; } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> m >> s; for (int i = 1; i <= n - 1; i++) { int x, y; cin >> x >> y; edges[x].push_back(y); edges[y].push_back(x); } dfs(s, s); for (int i = 1; i <= m; i++) { int a, b; cin >> a >> b; cout << query(a, b) << "\n"; } } |
Tarjan:洛谷70分，O2 100分
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 | #include<iostream> #include<vector> #include<algorithm> #include<cstring> using namespace std; int n, m, s; vector<int> edges[500005],askPair[500005]; bool visited[500005]; int father[500005]; inline int _find(int node) { if (father[node]==-1)return node; return father[node] = _find(father[node]); } inline void _union(int x, int y) { if(_find(x)!=_find(y))father[_find(x)] = y; } struct ask { int u, v; int ans; }asks[500005]; inline int checkV(int id,int node) { if (asks[id].u != node)return asks[id].u; return asks[id].v; } void dfs(int node,int fath) { for (int i = 0; i < edges[node].size(); i++) { if (edges[node][i] == fath)continue; dfs(edges[node][i],node); _union(edges[node][i], node); } visited[node] = true; for (int i = 0; i < askPair[node].size(); i++) { int v = checkV(askPair[node][i], node); if (visited[v])asks[askPair[node][i]].ans = _find(v); } } int main() { memset(father, -1, sizeof(father)); ios::sync_with_stdio(false); cin.tie(0); cin >> n >> m >> s; for (int i = 1; i <= n - 1; i++) { int x, y; cin >> x >> y; edges[x].push_back(y); edges[y].push_back(x); } for (int i = 1; i <= m; i++) { cin >> asks[i].u >> asks[i].v; askPair[asks[i].u].push_back(i); askPair[asks[i].v].push_back(i); } dfs(s,s); for (int i = 1; i <= m; i++)cout << asks[i].ans << "\n"; } |