| 1 | #include "../data-structures/union_find.cpp" |
| 2 | struct tarjan_olca { |
| 3 | int *ancestor; |
| 4 | vi *adj, answers; |
| 5 | vii *queries; |
| 6 | bool *colored; |
| 7 | union_find uf; |
| 8 | tarjan_olca(int n, vi *_adj) : adj(_adj), uf(n) { |
| 9 | colored = new bool[n]; |
| 10 | ancestor = new int[n]; |
| 11 | queries = new vii[n]; |
| 12 | memset(colored, 0, n); } |
| 13 | void query(int x, int y) { |
| 14 | queries[x].push_back(ii(y, size(answers))); |
| 15 | queries[y].push_back(ii(x, size(answers))); |
| 16 | answers.push_back(-1); } |
| 17 | void process(int u) { |
| 18 | ancestor[u] = u; |
| 19 | rep(i,0,size(adj[u])) { |
| 20 | int v = adj[u][i]; |
| 21 | process(v); |
| 22 | uf.unite(u,v); |
| 23 | ancestor[uf.find(u)] = u; } |
| 24 | colored[u] = true; |
| 25 | rep(i,0,size(queries[u])) { |
| 26 | int v = queries[u][i].first; |
| 27 | if (colored[v]) { |
| 28 | answers[queries[u][i].second] = ancestor[uf.find(v)]; |
| 29 | } } } }; |
| 30 | // vim: cc=60 ts=2 sts=2 sw=2: |
nothing calls this directly
no outgoing calls
no test coverage detected