12月6日星期六9:00-12:00
S+02L03【入门】欧拉路
描述
有一个无向图，图中要么有两个奇点要么0奇点，如果是欧拉回路请从第一个点为起点开始遍历，如果有两个奇点，则以字典序大的为起点开始遍历，在遍历的过程中，字典序小结点的先遍历。
请输出满足条件的欧拉路或者欧拉回路。
输入描述
第一行两个整数，n和e，表示有n个结点（结点编号为1~n），e条边。（5<=n<=20,5<=e<=15）
接下来e行，每行有2个数，代表这两个结点之间有一条边。（本题数据保证两个结点之间最多只有1条边，确保本题存在欧拉路或者欧拉回路）
输出描述
只有一行，为满足条件的欧拉路或欧拉回路。
用例输入 1
5 5
1 2
2 3
3 4
4 5
5 1
用例输出 1
1 2 3 4 5 1
代码
#include<bits/stdc++.h>
using namespace std;
int n,m,k;
int num[21][21];//邻接矩阵
int d[50];//节点的度
int r[50];//存走过的点
void dfs(int x){
for(int i=1;i<=n;i++){
if(num[x][i]==1){
//到这个点,开始拆边 防止死循环(相当于走过不在走了)
num[x][i]=0;
num[i][x]=0;
dfs(i);
}
}
k++;
r[k]=x;
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
int q,w;
cin>>q>>w;
num[q][w]=1;
num[w][q]=1;
d[q]++;
d[w]++;
}
// 判断有无奇点 没有的话就默认从1开始 有的话就赋值给s
int s = 1;
for(int i=n;i>=1;i--){
if(d[i]%2==1){
s = i;
break;
}
}
dfs(s);
for(int i=k;i>=1;i--){
cout<<r[i]<<" ";
}
return 0;
}
S+02Z01【基础】骑马修栅栏
描述
农民John每年有很多栅栏要修理。他总是骑着马穿过每一个栅栏并修复它破损的地方。
John是一个与其他农民一样懒的人。他讨厌骑马，因此从来不两次经过一个栅栏。你必须编一个程序，读入栅栏网络的描述，并计算出一条修栅栏的路径，使每个栅栏都恰好被经过一次。John能从任何一个顶点(即两个栅栏的交点)开始骑马，在任意一个顶点结束。
每一个栅栏连接两个顶点，顶点用1到500标号(虽然有的农场并没有500个顶点)。一个顶点上可连接任意多(>=1)个栅栏。所有栅栏都是连通的(也就是你可以从任意一个栅栏到达另外的所有栅栏)。
你的程序必须输出骑马的路径(用路上依次经过的顶点号码表示)。我们如果把输出的路径看成是一个500进制的数，那么当存在多组解的情况下，输出500进制表示法中最小的一个 (也就是输出第一个数较小的，如果还有多组解，输出第二个数较小的，等等)。 输入数据保证至少有一个解。
输入描述
第1行: 一个整数F(1 <= F <= 1024)，表示栅栏的数目
第2到F+1行: 每行两个整数i, j(1 <= i,j <= 500)表示这条栅栏连接i与j号顶点。
输出描述
输出应当有F+1行，每行一个整数，依次表示路径经过的顶点号。注意数据可能有多组解，但是只有上面题目要求的那一组解是认为正确的。
用例输入 1
9
1 2
2 3
3 4
4 2
4 5
2 5
5 6
5 7
4 6
用例输出 1
1
2
3
4
2
5
4
6
5
7
代码
#include<bits/stdc++.h>
using namespace std;
int n,k,mmax=INT_MIN;//记录结点最大编号
int num[510][510];//邻接矩阵
int d[510];//每个结点的度
int r[510];//存走过的点
void dfs(int x){
for(int i=1;i<=mmax;i++){
//判断和x有没有边
if(num[x][i]>=1){
//到i点 把x到i这条边删除 防止重复循环
num[x][i]--;
num[i][x]--;
dfs(i);
}
}
//递归结束回溯时,依次把没边的点放入数组r
r[++k]=x;
}
int main() {
cin>>n;
for(int i=0;i<n;i++){
int q,w;
cin>>q>>w;
num[q][w]++;
num[w][q]++;
d[q]++;
d[w]++;
mmax = max(mmax,max(q,w));
}
//题目要求优先从小到大的结点输出
//找最小的奇数边结点
int s = 0,jishu=0;
for(int i=1;i<=mmax;i++){
if(d[i]%2==1){
jishu++;
if(s==0) s=i;
}
}
if(jishu==1&&jishu>=3){
cout<<"No";
}else if(jishu==0){
s=1;
}
//开始递归
dfs(s);
//因为是回溯的时候存的值,所以是逆序存储 需要逆序打印
for(int i=k;i>=1;i--){
cout<<r[i]<<endl;
}
return 0;
}