为什么这个思路是错的,求hank
查看原帖
为什么这个思路是错的,求hank
1374261
gaohongyuan楼主2025/7/20 23:21
#include<bits/stdc++.h>
using namespace std;
vector<int> g[100005];
int b[100005];
int n,m,u,v,rd[100005],cd[100005],ans[100005],s=1,cnt1,cnt2,flag;

void dfs(int x,int k)
{
    if(flag)return;
    if(k==m+1)
    {
        cout<<s<<' ';
        for(int i=1;i<=m;i++)cout<<ans[i]<<' ';
        flag=1;
        return;
    }
    for(int i=b[x];i<g[x].size();i++)
    {
        b[x]++;
        ans[k]=g[x][i];
        dfs(g[x][i],k+1);
        if(flag)return;
    }
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>u>>v;
        g[u].push_back(v);
        rd[v]++;
        cd[u]++;
    }
    for(int i=1;i<=n;i++)
    {
        if(rd[i]+1!=cd[i]&&rd[i]!=cd[i]&&rd[i]!=cd[i]+1)
        {
            cout<<"No";
            return 0;
        }
        if(rd[i]+1==cd[i])s=i,cnt1++;
        if(rd[i]==cd[i]+1)cnt2++;
    }
    if(cnt1!=cnt2||cnt1+cnt2!=0&&cnt1+cnt2!=2)
    {
        cout<<"No";
        return 0;
    }
    for(int i=1;i<=n;i++)sort(g[i].begin(),g[i].end());
    dfs(s,1);
    /*for(int i=1;i<=n;i++)
    {
        for(int j=0;j<g[i].size();j++)
        cout<<g[i][j]<<' ';
        cout<<endl;
    }*/
    return 0;
}

交了可以看到AC #6 #10,#6是无解 我按第一篇TJ写的,不然9个T飞

2025/7/20 23:21
加载中...