洛谷 P1718 图形复原
2024-08-31 16:20:06
题目描述
HWX小朋友对几何的热爱在电脑组是出了名的,号称“每题必解”,这天,LXC在玩logo的时候突然想到了一个题目,刚好可以去测试一下他封号的虚实,于是,他logo编程画了一个n边形,并且将n个顶点用1,2,3,…,n这n个连续自然数随手编了个号,为了增加难度,他又画了一些不相交的对角线。如下图:
他把所有的边和对角线都写在一张纸上,对于上图,他写了:(1,3),(3,2),(2,4),(4,5),(5,1),(1,4),(3,4)。正得意的时候,电脑突然自动重启了,郁闷的是,他忘记保存刚才的logo程序了,此刻的他很想利用纸上记录的信息将这个n边形的编号复原,电脑组的你能帮助他吗?
输入输出格式
输入格式:
第一行n(n<=50)
下面若干行,每行两个数a,b,表示纸上记录的信息。
输出格式:
仅一行,按字典序较小的顺序依次输出顶点的编号。对于上面的例子,你的输出应该是1 3 2 4 5。
输入输出样例
输入样例#1: 复制
5
1 3
3 2
2 4
4 5
5 1
1 4
3 4
输出样例#1: 复制
1 3 2 4 5
思路:搜索。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n,m;
int ans[],vis[],map[][];
bool dfs(int now,int tot){
if(tot==n+&&now==) return true;
for(int i=;i<=n;i++)
if(map[now][i]&&!vis[i]){
vis[i]=;map[now][i]=map[i][now]=;ans[tot]=i;
if(dfs(i,tot+)) return true;
vis[i]=;map[now][i]=map[i][now]=;
}
return false;
}
int main(){
scanf("%d",&n);
int a,b;
while(scanf("%d%d",&a,&b)!=EOF)
map[a][b]=map[b][a]=;
dfs(,);
cout<<""<<" ";
for(int i=;i<n;i++)
cout<<ans[i]<<" ";
}
最新文章
- linux 共享内存 shmat,shmget,shmdt,shmctl
- 【leetcode❤python】 155. Min Stack
- css 单位-px、em、rem、百分比
- tomcat文件服务配置
- -Xbootclasspath参数、java -jar参数运行应用时classpath的设置方法
- Sql语句批量更新数据(多表关联)
- MVC自学第四课
- Java集合框架Collection
- lesson - 4 笔记 /inode / suid / sgid / sbit / chmod /umask / chown / rwx / wc /grep / tr / sort / cut /which / whereis / locate / find / ln /
- 大神教你如何解决Linux系统80端口被占用
- Django数据库,在原有表中添加新字段
- Neural Network Virtual Machine
- <;转>; mysql处理高并发,防止库存超卖
- K - Video Reviews Gym - 101755K (二分)
- IObservable 接口
- PTA 根据后序和中序遍历输出先序遍历(25 分)
- 撩课-Web大前端每天5道面试题-Day33
- dbca时报错:ORA-12705(NLS_LANG=AMERICAN_AMERICA.UTF8);
- 一键切换hosts文件
- MySQL必知必会笔记(六)存储过程 游标 触发器
热门文章
- Gradle学习之自己定义属性
- 【C#】报表制作&;lt;机房重构&;gt;
- Random numbers
- Kali linux 2016.2(Rolling)里Metasploit连接(包括默认和自定义)的PostgreSQL数据库之后的切换到指定的工作空间
- Spring SpEL in JSP and Assign SpEL value to Java variable in JSP
- 2018年湘潭大学程序设计竞赛 Fibonacci进制
- GoldenGate 性能优化方法
- ReactiveCocoa使用记录-网络登录事件
- Scala和范畴论 -- 对Monad的一点认识
- 陌上开花(CDQ分治)