社区讨论
为啥啊?不懂
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 条回复,欢迎继续交流。
正在加载回复...