#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<set>
#include<string>
#include<iomanip>
#include<cstring>
#include<ctime>
#include<unordered_map>
#include<stack>
#include<queue>
//*****************************************************************************************************************
//                .-~~~~~~~~~-._       _.-~~~~~~~~~-.
//            __.'              ~.   .~              `.__
//          .'//                  \./                  \\`.
//        .'//                     |                     \\`.
//      .'// .-~"""""""~~~~-._     |     _,-~~~~"""""""~-. \\`.
//    .'//.-"                 `-.  |  .-'                 "-.\\`.
//  .'//______.============-..   \ | /   ..-============.______\\`.
//.'______________________________\|/______________________________`.
//*****************************************************************************************************************
using namespace std;
const int o = 1e7 + 10;
typedef pair<long, long>ll;
int a[o],s[o],b[o];
int main()
{
    int n, q;
    cin >> n >> q;
    while(n--)
    {
        int x, y;
        cin >> x >> y;
        a[y] = x;//用指针把终点和起点连接起来
    }
    while (q--)
    {
        int t,c=0;
        cin >> t;//用于找每一个终点的起点（比较拗口，大概就是，知道是4，用t找3，然后t为3，然后找0）
        b[c++] = t;
        while (a[t])
        {
            b[c++] = a[t];//逆向保存路径，便于输出
            t = a[t];
        }
        for (int i = c; i >= 0; i--)
        {
            cout << b[i] << " ";
        }
        cout << endl;//比起其他的题目，这个题目不用\n就能过
    }
}

题目给出不会有重边和环，正向考虑相当于一条路有多条分叉，一个出口只会对应一个入口，因此倒着考虑比较合适，自然而然想到递归的解法 思路： 建立一个哈希表来存储出口所对应的入口，如实例给的1对应0，只需记录hash[1]=0;存入后递归输出相应的值即可。 `

代码如下

using namespace std;
int n,q,x,y;
int target[1005];//定义出口数组
int main(){
ios_base::sync_with_stdio(0);//输入量较大，关闭同步流，或者是用printf and scanf
cin.tie(0);cout.tie(0);
cin>>n>>q;
unordered_map<int,int>hash;//建立哈希表
for(int i=0;i< n;i++){
cin>>x>>y;
hash[y]=x;//对应入口存入hash表
}
//递归解决问题
auto dfs=[&](auto&&dfs,int x)->void{
//x==0输出并返回
if(!x){
cout<<x<<' ';
return;
}
dfs(dfs,hash[x]);//递归调用后输出
cout<<x<<' ';
return;
};
for(int i=0;i<q;i++)cin>>target[i];
for(int i=0;i<q;i++){
dfs(dfs,target[i]);//调用递归表达式
cout<<'\n';
}
return 0;
}

时间复杂度：O(qn); 空间复杂度：O(qn); //希望我的题解对你有帮助

给的时间限制是2s，感觉就是为了暴力用的。 无重环即可以一对多而不能多对一，循环找到door为0即可。

#include<stdio.h>

#include algorithm//加括号

#define N 100005

using namespace std;

struct node

{

int door;

int t;

}s[N];

int cmp(node a,node b)

{

if(a.t<b.t)

{

return 1;

}

return 0;

}

int main()

{

int n,q,z;

scanf("%d %d",&n,&q);

for(int i=1;i<=n;i++)

{

scanf("%d %d",&s[i].door,&s[i].t);

}

sort(s+1,s+n+1,cmp);

while(q--)

{

scanf("%d",&z);

if(s[z].door==0)

{ printf("0 %d\n",z);

}

else

{

int mm[N];

for(int i=0;i<=N;i++)

{

mm[i]=-1;

}

int cnt=0;

mm[cnt]=s[z].door;

while(mm[cnt]!=0)

{

for(int i=1;i<=n;i++)

{

if(s[i].t==mm[cnt])

{

mm[++cnt]=s[i].door;

break;

}

}

} for(int j=cnt;j>=0;j--)

{

printf("%d ",mm[j]);

}

printf("%d\n",z);

}

}

}

#include<stdio.h> #include<algorithm>//dfs与结构体的结合 #include<iostream> using namespace std; struct hui { int x,y;

}arr[100000]; int brr[1000]; int n,q,t=0; void dfs(int g) { if(arr[g].x0) { printf("0 "); for(int i=t;i>=0;i--) { printf("%d ",brr[i]); } printf("\n"); return; } for(int i=1;i<=n;i++) { if(arr[i].yg) { t++; brr[t]=arr[i].x; dfs(arr[i].x); } }

} int main() {

scanf("%d%d",&n,&q); for(int i=1;i<=n;i++) { scanf("%d%d",&arr[i].x,&arr[i].y); } while(q--) { int g; scanf("%d",&g); brr[0]=g; t=0; dfs(g);

}

return 0;

}

#include
#define int long long
#define IO ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
const int N=2e5+10, f=1e9;
int a[N];
map<int ,int>mp;
void digui(int n)
{
    if(n==0) return;
    digui(mp[n]);
    cout << n << " ";
}

void solve()
{
	int n,q;
    cin >> n >> q;
    
    for(int i=1;i<=n;i++){
        int fi,en;
        cin >> fi >> en;
        mp[en]=fi;  // en的前驱是fi        
    }
    for(int i=1;i<=q;i++){
        int po=-1;
        cin >> po;
        cout << 0 << " ";
        digui(po);
        cout << '\n';
    }


}
signed main ()
{
	
	IO;
	int T = 1;
	// cin >> T;
	while(T--) solve();
	return 0;
//}

6