11 • 8个月前
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int map[10001][10001];//记录两个点之间的路径个数
int du[10001];//辅助记录奇点
int lu[10001];//记录路径
int n,x,y,js=0;
int maxn=0;
void find(int i)//
{
int j;
for(j=1;j<=maxn;++j)//而且这里不是n而是maxn因为n不是点的个数而是下面有多少行
{
if(map[i][j]>=1)
{
map[i][j]--;//删去边一次吗避免重复
map[j][i]--;//z这里和一笔画不一样这里是累减而一笔画直接变成0
find(j);
}
}
lu[++js]=i;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i)
{
scanf("%d%d",&x,&y);
map[x][y]++;
map[y][x]++;
du[x]++;
du[y]++;//记录出现的次数
maxn=max(maxn,max(x,y));
}
int start=1;//默认奇点是1
for(int i=1;i<=maxn;++i)
{
if(du[i]%2)//找到奇点
{
start=i;//记录奇点
break;//然后结束循环
}
}
find(start);//从奇点开始找
for(int i=js;i>=1;i--)
{
printf("%d\n",lu[i]);//挨个输出路径并且换行
}
return 0;
}
评论:
#include<iostream>
#include<vector>
using namespace std;
int map[501][501]; //i到j有几条边
int deg[501];
int maxPoint = 0, minPoint = 501, f;
int ans[1025];
int order = 0;
void dfs(int node) { //node表示当前所在点 ,count表示已经走过的边的数量
for (int i = minPoint; i <= maxPoint; i++) if (map[node][i]) {
map[node][i]--;
map[i][node]--;//因为是无向边，所以记得两个都改
dfs(i);
}
ans[order++] = node;
}
int main() {
int from, to;
cin >> f;
for (int i = 0; i < f; i++) {
cin >> from >> to;
map[from][to]++;
map[to][from]++;
deg[from]++;
deg[to]++;
maxPoint = max(maxPoint, from);
maxPoint = max(maxPoint, to);
minPoint = min(minPoint, from);
minPoint = min(minPoint, to);
}
int startPoint = 0;
for (int i = minPoint; i <= maxPoint; i++) {//找有没有奇点
if (deg[i] % 2 == 1) {
startPoint = i;
break;
}
}
if (startPoint == 0) //如果我们找到了一个奇点
{
startPoint = minPoint;
}
dfs(startPoint);
for (int i = f; i >= 0; i--) cout << ans[i] << endl;
return 0;
}
请先登录，才能进行评论