AT D
  • 板块学术版
  • 楼主x1489631649
  • 当前回复9
  • 已保存回复11
  • 发布时间2025/8/2 22:00
  • 上次更新2025/8/3 14:11:44
查看原帖
AT D
780505
x1489631649楼主2025/8/2 22:00

正解是DFS吗,如果是的话求调

#include<bits/stdc++.h>
using namespace std;
vector<int> e[1005];
int a[1005],v[1005];
int S,E;
int fl=0;
void dfs(int st,int p)
{
    if (fl==1)
    {
        return ;
    }
    a[st]=p;
    if (p==E)
    {
        for (int i=1;i<=st;i++)
        {
            printf("%d ",a[i]);
        }
        printf("\n");
        fl=1;
        return ;
    }
    for (int i:e[p])
    {
        if (v[i]==0)
        {
            v[i]=1;
            dfs(st+1,i);
            v[i]=0;
        }
    }
}
int main()
{
//    freopen(".in","r",stdin);
//    freopen(".out","w",stdout);
    int T;
    scanf("%d",&T);
    while (T--)
    {
        int n,m;
        scanf("%d%d%d%d",&n,&m,&S,&E);
        for (int i=1;i<=n;i++)
        {
            e[i].clear();
        }
        for (int i=1;i<=m;i++)
        {
            int t1,t2;
            scanf("%d%d",&t1,&t2);
            e[t1].push_back(t2);
            e[t2].push_back(t1);
        }
        for (int i=1;i<=n;i++)
        {
            sort(e[i].begin(),e[i].end());
        }
        memset(v,0,sizeof(v));
        v[S]=1;
        fl=0;
        dfs(1,S);
    }
    return 0;
}
2025/8/2 22:00
加载中...