我要评论题意： 有n个珠子。每个珠子有两种颜色，分布在珠子的两边。一共有50种不同的颜色。把这些珠子串起来，要求两个相邻的珠子接触的部分颜色相同。问是否能连成一个珠串项链？如果能，打印出一种连法。
题解： 一开始看样例其实我有点懵 ，每行给出某个珠子的两个颜色，然后相同颜色的能相连。其实我们换个角度，把行输入看成是一条边（原本代表一个珠子的两个颜色），把每种颜色看成一个点。那么我们的任务就简单明了了，把所有的颜色连起来，每条边通过且只通过一次——欧拉回路。
- 连通。 一般情况下是需要用DFS、并查集等方法来判断图的连通性的，但是这道题比较简单，用不上；给出的图都是能够连通的。
- 判断欧拉回路。 首先明确这是一个无向连通图，而无向连通图中欧拉回路的判断条件就是图中的点全都是偶点。
- 输出欧拉回路。 用DFS即可。但注意程序中递归要在输出之前！
#include<iostream>
#include<cstring>
using namespace std;
const int N = 1e3 + 10;
int T, cnt, n, a, b;
int deg[N], G[N][N];
bool check(){ for(int i = 1; i <= 50; i++) if(deg[i] % 2) return false; return true;}
void euler(int u){
for(int v = 1; v <= 50; v++){
if(G[u][v]){
G[u][v]--, G[v][u]--;
euler(v); ／／先递归再输出
printf("%d %d\n", v, u);
}
}
}
int main(){
scanf("%d", &T);while(T--){
memset(deg, 0, sizeof deg);
memset(G, 0, sizeof G);
scanf("%d", &n);
for(int i = 0; i < n; i++){
scanf("%d%d", &a, &b);
deg[a]++, deg[b]++;
G[a][b]++, G[b][a]++;
}
printf("Case #%d\n", ++cnt);
if(!check()) printf("some beads may be lost\n");
else euler(b);
puts("");
}
return 0;
}
本文地址：https://blog.csdn.net/m0_46187157/article/details/108184606
您可能感兴趣的文章:
如您对本文有疑问或者有任何想说的，请 点击进行留言回复，万千网友为您解惑！
网友评论