点击打开链接uva 10054
思路: 欧拉回路
分析:
1 对于一个无向图来说如果这个图是一个欧拉图,那么必须满足该图是连通的并且每个点的度数都是偶数
2 题目给定n条边的无向图问我们是否是一个欧拉图,是的话输出欧拉图的一条路径
3 首先我们先判断是否所有点的度数都是偶数,然后我们去判断当前图是否是只有一个连通分支,那么这个利用并查集即可
4 如果都满足的话直接去搜索并且输出路径即可
代码:
#include<stack>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN = 55;
int father[MAXN] , degree[MAXN];
int n , mat[MAXN][MAXN];
void init(){
memset(mat , 0 , sizeof(mat));
memset(degree , 0 , sizeof(degree));
for(int i = 0 ; i < MAXN ; i++)
father[i] = i;
}
int find(int x){
if(x != father[x])
father[x] = find(father[x]);
return father[x];
}
bool isOk(){
int root = -1;
for(int i = 0 ; i < MAXN ; i++){
if(degree[i]&1)
return false;
if(degree[i]){
if(root == -1)
root = find(i);
else{
if(root != find(i))
return false;
}
}
}
return true;
}
void dfs(int cur){
for(int i = 1 ; i < MAXN ; i++){
if(mat[cur][i]){
mat[cur][i]--;
mat[i][cur]--;
dfs(i);
printf("%d %d\n" , i , cur);
}
}
}
int main(){
int Case = 1 , T , x , y , start;
bool isFirst = true;
scanf("%d" , &T);
while(T--){
scanf("%d" , &n);
init();
for(int i = 0 ; i < n ; i++){
scanf("%d%d", &x , &y);
start = x;
mat[x][y]++;
mat[y][x]++;
degree[x]++;
degree[y]++;
father[find(x)] = find(y);
}
if(isFirst)
isFirst = false;
else
printf("\n");
printf("Case #%d\n" , Case++);
if(!isOk())
printf("some beads may be lost\n");
else
dfs(start);
}
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