题解：SP3374 SCAVHUNT - Scavenger Hunt

cy950469 · 2026-10-20 18:48:41 · 题解

题目大意

有 s 组关系，表示后者在前者之后，结果所有关系可以组成一条链，从头到尾输出这条链。

思路

考虑 dfs。

由于图中所有节点元素都是 string，可以用 map 存图。先标记入度，求出起点后 dfs，边遍历边输出即可。

代码

#include<bits/stdc++.h>
using namespace std;
int s;
map<string,int> rd; //记录入度
map<string,string> g; //存图
void dfs(string u)
{
    cout<<u<<'\n';
    if(g.count(u)) dfs(g[u]);
}
int main()
{
    int t;
    cin>>t;
    for(int i=1;i<=t;i++)
    {
        rd.clear();
        g.clear(); //多测清空
        cin>>s;
        for(int j=1;j<s;j++)
        {
            string u,v;
            cin>>u>>v;
            rd[v]++;
            g[u]=v;
            rd[u]; //千万记得这个，否则rd中不存在起点的节点。
        }
        cout<<"Scenario #"<<i<<":\n";
        for(auto j:rd)
        {
            if(j.second==0)
            {
                dfs(j.first);
            }
        }
        cout<<'\n';
    }
    return 0;
}