点击打开链接
题目意思:有一堆散落的项链的的珠子,珠子有可能重复的出现,问我们能否连接成一条项链,要求该项链的每一节的两个珠子要满足,“第一个珠子必须和前一节的第二个珠子相同,对于最后一节的第二个珠子必须和第一节的第一个相同“。问能否实现,如果可以输出其中一种路径
解题思路:题目意思是判断是否可以连乘一个环,满足欧拉回路的条件,那么题目就转化为给个一个欧拉路判断是否是连通。我们知道对于判断欧拉道路是否是连通的我们都是采用建立一个无向图的邻阶矩阵,然后输出操作
第一步:任何一条欧拉回路满足所有的度数和为偶数,那么先判断是否满足该条件,不满足直接退出
第二步:我么在邻阶矩阵map中找到一个有出度的点进行路径搜索 , 对于路径的输出,我们一般用递归,利用栈来存储节点的坐标,最后逆序输出。
代码:
//对于项链是否可以满足索给的条件,那么我们先判断输入的数据是否是欧拉回路,即度数的和是否全部为偶数,如果是我们再去打印出一条路径
#include <iostream>
#include <cstdio>
#include <cctype>
#include <stack>
#include <cstring>
#include <cstdlib>
using namespace std;
const int MAXN = 60;
//结构体存储两个对应的坐标
struct node{
int x;
int y;
};
node p;
int t , n;
int map[MAXN][MAXN];//无向图的邻阶矩阵(搜索路径或判断连通都要用无向图的邻阶矩阵)
int eur[MAXN];//存储每个节点的度数
int flag;
stack<node>s;//栈用来存储节点的坐标
//
inline void output(int u){
for(int i = 0 ; i <= 50 ; i++){
if(map[u][i]){
--map[u][i];//相应点减1
--map[i][u];
output(i);//继续向下搜索
node temp;
temp.x = u ; temp.y = i;
s.push(temp);//把点压入栈中(逆序输出)
}
}
}
//
inline void solve(){
int i , j , temp;
temp = 0;
for(i = 1 ; i <= 50 ; i++){
for(j = 1; j <= 50 ; j++){
if(map[i][j]){
output(i);//找到有出度的点开始搜索路径
temp = 1;
break;//直接跳出
}
}
if(temp)
break;//直接跳出
}
while(!s.empty()){//输出结果
node temp = s.top();
printf("%d %d\n" , temp.x , temp.y);
s.pop();
}
}
//
int main(){
int i , k;
int x , y;
scanf("%d" , &t);
for(k = 1 ; k <= t ; k++){
scanf("%d" , &n);
flag = 1;
memset(map , 0 , sizeof(map));
memset(eur , 0 , sizeof(eur));
for(i = 0 ; i < n ; i++){
scanf("%d%d" , &x , &y);
map[x][y]++;//邻阶矩阵的建立
map[y][x]++;
eur[x]++;//度数加1
eur[y]++;
}
for(i = 0 ; i <= 50 ; i++){//判断满足欧拉回路
if(eur[i] %2 != 0){
flag = 0;
break;
}
}
printf("Case #%d\n" , k);
if(flag == 0)//不满足欧拉回路直接输出
printf("some beads may be lost\n");
else
solve();
if(k != t)
printf("\n");//最后没有空行
}
return 0;
}
分享到:
相关推荐
判断输入字符串是否为镜像或回文串。 来源于UVaOJ - 401. 水题。
开源项目-codingsince1985-UVa#uva-online-judge-solutions-in-golang.zip,两年来每天都在解决一个uva在线裁判问题,算起来…
uva705 Slash Maze 的代码,在UVaOJ上通过
PDF试题
uva532 Dungeon Master的源代码,并且AC了
Algorithm-UVA-Solutions-in-Python.zip,python 3中各种uva(acm)问题的解决方案。,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
这是UVA133 TheDoleQueue救济金发放问题,经典的算法问题。初学算法的人要对这种算法非常熟悉并且能熟练运用。
tpcw-nyu-uva-client 客户端
leetcode 2 算法-Java UVa Online Judge(ACM-ICPC Live ...使用:数组、哈希表、链表、二分搜索、动态规划、堆栈、堆、reedy、排序、树 DFS、BFS、图、二分搜索树、递归、记忆、队列、映射等。...Uva-ACM-ICPC