社区讨论

为啥啊?不懂

P7771【模板】欧拉路径参与者 2已保存回复 5

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
5 条
当前快照
1 份
快照标识符
@miispydz
此快照首次捕获于
2025/11/28 19:45
3 个月前
此快照最后确认于
2025/11/29 16:35
3 个月前
查看原帖
CPP
#include<bits/stdc++.h>
using namespace std;
/*

*/
struct FSI{
    template<typename T>
    FSI& operator >> (T &res){
        res=0;T f=1;char ch=getchar();
        while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
        while (isdigit(ch)){res=res*10+ch-'0';ch=getchar();}
        res*=f;
        return *this;
    }
}scan;
const int N=1e5+10;
int n,m,i,x,y;
int c1,c2,pos;
int f[N];
vector<int> G[N];
int din[N],dout[N];
bool vis[N];
int st[N],tp;
void dfs(int x)
{
    int to;
    for (;f[x]<G[x].size();)
    {
        to=G[x][f[x]];
        f[x]++;
        if (!vis[to]) dfs(to);
    }
    st[++tp]=x;
}
int main()
{
    scan>>n>>m;
    for (i=1;i<=m;i++)
    {
        scan>>x>>y;
        dout[x]++;
        din[y]++;
        G[x].push_back(y);
    }
    for (i=1;i<=n;i++) sort(G[i].begin(),G[i].end());
    for (i=1;i<=n;i++)
    {
        if (din[i]-dout[i]==1) c1++;
        else if (dout[i]-din[i]==1) c2++;
        else if (din[i]!=dout[i])
        {
            puts("No");
            return 0;
        }
    }
    if (c1>1||c2>1)
    {
        puts("No");
        return 0;
    }
    pos=1;
    for (i=1;i<=n;i++)
    {
        if (dout[i]-din[i]==1) pos=i;
    }
    dfs(pos);
    for (i=tp;i>=1;i--) printf("%d ",st[i]);
    return 0;
}
这是错误代码。
CPP
#include<bits/stdc++.h>
using namespace std;
/*

*/
struct FSI{
    template<typename T>
    FSI& operator >> (T &res){
        res=0;T f=1;char ch=getchar();
        while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
        while (isdigit(ch)){res=res*10+ch-'0';ch=getchar();}
        res*=f;
        return *this;
    }
}scan;
const int N=1e5+10;
int n,m,i,x,y;
int c1,c2,pos;
int f[N];
vector<int> G[N];
int din[N],dout[N];
int st[N],tp;
bool vis[N];
void dfs(int x)
{
    int to;
    for (;f[x]<G[x].size();)
    {
        to=G[x][f[x]];
        f[x]++;
        if (!vis[to]) dfs(to);
    }
    st[++tp]=x;
}
int main()
{
    scan>>n>>m;
    for (i=1;i<=m;i++)
    {
        scan>>x>>y;
        dout[x]++;
        din[y]++;
        G[x].push_back(y);
    }
    for (i=1;i<=n;i++) sort(G[i].begin(),G[i].end());
    for (i=1;i<=n;i++)
    {
        if (din[i]-dout[i]==1) c1++;
        else if (dout[i]-din[i]==1) c2++;
        else if (din[i]!=dout[i])
        {
            puts("No");
            return 0;
        }
    }
    if (c1>1||c2>1)
    {
        puts("No");
        return 0;
    }
    pos=1;
    for (i=1;i<=n;i++)
    {
        if (dout[i]-din[i]==1) pos=i;
    }
    dfs(pos);
    for (i=tp;i>=1;i--) printf("%d ",st[i]);
    return 0;
}
这是正确代码。
容易发现,两个代码的差别仅在于 vis[] 定义的位置。
为何?

回复

5 条回复,欢迎继续交流。

正在加载回复...