Cod sursa(job #2466426)

Utilizator paul_danutDandelion paul_danut Data 2 octombrie 2019 09:43:05
Problema Lowest Common Ancestor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.99 kb
#include <fstream>
#include <vector>

int findLCA(const std::vector<int>& parent, int x, int y)
{
    std::vector<bool> a(100001,0);
    bool isFound = false;
    int lca = 1;
    a[x] = true;
    a[y] = true;
    while(!isFound)
    {
        x = parent[x-1];
        y = parent[y-1];

        if(a[x])
        {
            lca = x;
            isFound = true;
        }
        a[x] = true;

        if( a[y])
        {
            lca = y;
            isFound = true;
        }
        a[y] = true;
    }
    return lca;
}

int main()
{
    std::ifstream fin("lca.in");
    std::ofstream fout("lca.out");

    auto n=0, m=0, x=0, y=0;
    fin>>n>>m;
    std::vector<int> parent;
    parent.push_back(1); // primul nod este nodul radacina

    for(auto i=0; i < n-1; ++i)
    {
        fin>>x;
        parent.push_back(x);
    }

    for(auto i=0; i < m; ++i)
    {
        fin >> x >> y;
        fout << findLCA(parent, x, y) << '\n';
    }

    return 0;
}