????

????

11 · 发布于 2024-08-02 · 浏览 499 回复 1 
#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;
}

全部回复 共 1 条

  1. ------监狱栅栏------ #1 · 
    #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;
}

发表回复