[C++知识库]用LUA（和C++）刷PAT (Advanced Level) ——1032 Sharing

N的上限是10^5就不要挣扎了…

#include <iostream>
#include <map>
#include <string>

using namespace std;

struct letter
{
    string data, next;
};

int main()
{
    map<string, letter> letters;
    map<string, bool> nexts;
    string s1, s2;
    int N;
    cin>>s1>>s2>>N;
    for (int i = 0;i < N; i++)
    {
        letter l;
        string key;
        cin>>key>>l.data>>l.next;
        letters[key] = l;
    }

    while (s1 != "-1")
    {
        nexts[s1] = true;
        s1 = letters[s1].next;
    }
    
    while (true)
    {
        if(s2 == "-1"||nexts[s2])
        {
            cout<<s2<<endl;
            break;
        }
        s2 = letters[s2].next;
    }
}