题目描述
Eulerian:度数都是偶数且连通
半:连通但度数不是偶数
错误1:
if(n==dfs(1)&&odd==0) puts("Eulerian");
else if(n==dfs(1)&&odd==2) puts("Semi-Eulerian");
第二次调用dfs(1)时,st【】用过了,都是true,答案不对,应该int cnt=dfs(1);
样例
int dfs(int u)
{
st[u]=true;
int h=1;
for(int i=1;i<=n;i++)
{
if(!st[i]&&g[u][i]) h=dfs(i)+h;
}
return h;
}
int main()
{
//freopen("1.txt","r",stdin);
cin>>n>>m;
for(int i=0;i<m;i++)
{
int a,b;cin>>a>>b;
g[a][b]=g[b][a]=1;
d[a]++,d[b]++;
}
int odd=0;
for(int i=1;i<=n;i++) if(d[i]%2!=0) odd++;
cout<<d[1];
for(int i=2;i<=n;i++) cout<<" "<<d[i];
cout<<endl;
int cnt=dfs(1);
// cout<<cnt;
if(n==cnt&&odd==0) puts("Eulerian");
else if(n==cnt&&odd==2) puts("Semi-Eulerian");
else puts("Non-Eulerian");
return 0;
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla