Eulerian Path-欧拉图-pat-1126
欧拉图、欧拉回路——边遍历欧拉图描述哈密顿图——点遍历以下投机取巧做法,难顶#include<iostream>#include<cstdio>#include<vector>using namespace std;const int N=500;vector<int> v[N];int main(){int n,m;int s,d;scanf("%
·
欧拉图、欧拉回路——边遍历
欧拉图描述
哈密顿图——点遍历
以下投机取巧做法,难顶
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
const int N=500;
vector<int> v[N];
int main()
{
int n,m;
int s,d;
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++)
{
scanf("%d%d",&s,&d);
v[s].push_back(d);
v[d].push_back(s);
}
int count=0;
for(int i=1;i<=n;i++)
{
if(i!=n)
printf("%d ",v[i].size());
if(v[i].size()%2==1)
count++;
if(i==n)
printf("%d\n",v[i].size());
}
if(count==0)
cout<<"Eulerian";
else if(count==2)
cout<<"Semi-Eulerian";
else
cout<<"Non-Eulerian";
return 0;
}
没有通过原因,没有判断连通性。这个问题在链表的中也经常存在,需要注意
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
const int N=5000;
bool visit[N];
vector<int> v[N];
int cnt=0;
void dfs(int index)
{
visit[index]=true;
cnt++;
for(int i=0;i<v[index].size();i++)
{
if(visit[v[index][i]]==false)
{
dfs(v[index][i]);
}
}
}
int main()
{
int n,m;
int s,d;
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++)
{
scanf("%d%d",&s,&d);
v[s].push_back(d);
v[d].push_back(s);
}
int count=0;
for(int i=1;i<=n;i++)
{
if(i!=n)
printf("%d ",v[i].size());
if(v[i].size()%2==1)
count++;
if(i==n)
printf("%d\n",v[i].size());
}
dfs(1);
if(count==0&&cnt==n)
cout<<"Eulerian";
else if(count==2&&cnt==n)
cout<<"Semi-Eulerian";
else
cout<<"Non-Eulerian";
return 0;
}
更多推荐
已为社区贡献3条内容
所有评论(0)