大神的世界

每一個節點都記錄自己的 parent

則找尋兩節點的距離，即找尋距離兩節點最近的共同 parent

將兩節點所需路徑加總，即為所求

太久沒寫程式題了，都在打 CTF , 寫了一個爛爛 ( 低效率) 的程式

#include <iostream>
#include <sstream>
#include <vector>

using namespace std;

constexpr int MAX_PEOPLE_NUM = 50000;

struct People
{
    string m_name;
    string m_parent;
    People *m_to_parent = nullptr;
};

int main()
{
    People p_obj[MAX_PEOPLE_NUM];
    int people_num;

    int case_num;
    while(cin >> case_num)
    {
        people_num = 0;
        for(int i = 0; i<case_num; i+=1){
            string parent;
            cin >> parent;

            int p0;
            for(p0 = 0; p0 < people_num; p0+=1)
                if(p_obj[p0].m_name == parent) break;

            if(p0 == people_num){    
                p_obj[p0].m_name = parent;
                p_obj[p0].m_parent = "";
                p_obj[p0].m_to_parent = nullptr;
                people_num += 1;
            }

            string child;
            getline(cin, child);
            istringstream iss(child);

            while(iss >> child){
                int p;
                for(p = 0; p < people_num; p+=1){
                    if(p_obj[p].m_name == child){
                        p_obj[p].m_parent = parent;
                        p_obj[p].m_to_parent = &p_obj[p0];
                        break;
                    }
                }

                if(p == people_num){    
                    p_obj[p].m_name = child;
                    p_obj[p].m_parent = parent;
                    p_obj[p].m_to_parent = &p_obj[p0];
                    people_num += 1;
                }
            }
        }

        string name1, name2;
        cin >> name1 >> name2;

        int p;
        for(p = 0; p < people_num; p+=1)
            if(p_obj[p].m_name == name1) break;

        int cnt = 0;
        bool got = false;
        People *tmp = &p_obj[p];
        vector<string> relative;
        vector<int> level;

        while(tmp->m_to_parent && !got)
        {
            cnt += 1;

            if(tmp->m_parent == name2){
                got = true;
                break;
            }

            relative.push_back(tmp->m_parent);
            tmp = tmp->m_to_parent;
        }

        int v = cnt-1;
        while(v >= 0)
            level.push_back(v--);

        for(p = 0; p < people_num; p+=1)
            if(p_obj[p].m_name == name2) break;

        tmp = &p_obj[p];
        int ans = 0;
        
        while(tmp->m_to_parent && !got)
        {
            for(int v = 0; v < relative.size(); v+=1)
                if(tmp->m_parent == relative[v]){
                    ans += cnt - level[v];
                    got = true;
                    break;
                }

            ans += 1;
            tmp = tmp->m_to_parent;
        }

        if(ans == 0)
            ans = cnt;

        cout << ans << endl;

        relative.clear();
        level.clear();
    }
}