Hihocoder 1067

最近公共祖先二离线算法
/**/

#include <cstdio>

#include <cstring>

#include <cmath>

#include <cctype>

#include <iostream>

#include <algorithm>

#include <map>

#include <set>

#include <vector>

#include <string>

#include <stack>

#include <queue>

typedef long long LL;

typedef unsigned long long ULL;

using namespace std;

typedef pair<int, int> P;

#define x first

#define y second

#define pb push_back

bool Sqrt(LL n) { return (LL)sqrt(n) * sqrt(n) == n; }

const double PI = acos(-1.0), ESP = 1e-10;

const LL INF = 99999999999999;

const int inf = 999999999, N = 1e5 + 24;

vector<int> G[N];

vector<P> Q[N];

map<string, int> H;

string a, b, m[N];

int A, B, fa[N], n, k, c, ans[N];

int fnd(int x) { return x == fa[x] ? x : fa[x] = fnd(fa[x]); }

void dfs(int u, int p)

{

    fa[u] = u;

    for(auto v : G[u]) if(v != p) dfs(v, u);

    for(auto v : Q[u]) if(fa[v.x]) ans[v.y] = fnd(v.x);

    fa[u] = p;

}

int main()

{

    //freopen("in.txt", "r", stdin);

    //freopen("out.txt", "w", stdout);

    scanf("%d", &n);

    while(n--) {

        cin >> a >> b;

        if(!(A = H[a])) { A = H[a] = ++c; m[c] = a;}

        if(!(B = H[b])) { B = H[b] = ++c; m[c] = b;}

        G[A].pb(B); G[B].pb(A);

    }

    scanf("%d", &k);

    for(int i = 1; i <= k; i++) {

        cin >> a >> b;

        A = H[a]; B = H[b];

        Q[A].pb(P(B, i)); Q[B].pb(P(A, i));

    }

    dfs(1, 0);

    for(int i = 1; i <= k; i++) cout << m[ans[i]] << "\n";

    return 0;

}

/*

    input:

    output:

    modeling:

    methods:

    complexity:

    summary:

*/
巴特西

Hihocoder 1067

最新文章

热门文章
