UVA 10054

本文主要是介绍UVA 10054，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

/*欧拉回路*/
/*这到题UVA 虽然AC但是因为 给的数据有点弱，其实还有种情况：需要判断一下图是否是一个连通图，比如说如果最好串成了2条项链，而不能穿成一条，就应该输出不存在*/
//判断联通可以在最后输出前扫一下，很简单我就不写了
#include <stdio.h>
#include <string.h>
int map[200][200], vis[200][200];
int num[100];
typedef struct
{int u, v;
}p;
p stack[1000];
int top, n;
void push( int u, int v )
{stack[top].u = u;stack[top].v = v;top++;
}
p pop()
{return stack[--top]; 
}
void euler( int u )
{int v;for( v = 1; v <= 60; v++ )if( map[u][v] ){map[u][v]--;map[v][u]--;euler(v);push(u, v);}
}
int empty()
{if( top == 0 )return 1;return 0;
}
int main()
{freopen( "in", "r", stdin  );p ps;int T, i, j, cout = 0, u, v,flag, t;scanf( "%d", &T );while( T-- ){t = 0;flag = 0;memset( num, 0, sizeof(num) );memset(stack, 0, sizeof(stack) );memset(map, 0, sizeof(map) );memset(vis, 0, sizeof(vis) );scanf( "%d", &n );for( i = 1; i <= n; i++ ){scanf( "%d%d", &u, &v );if( u != v )t = 1;map[u][v]++;map[v][u]++;num[u]++;num[v]++;}if( !t ){printf( "Case #%d\n", ++cout );while( n-- )printf( "%d %d\n", u, v );printf( "\n" );continue;}for( i = 1; i <= 60; i++ )if( num[i] % 2 )flag = 1;if( flag ){printf( "Case #%d\n", ++cout );printf( "some beads may be lost\n\n" );}else{for( i = 1; i <= 60; i++ )if( num[i] > 0 ){euler( i );break;}   printf( "Case #%d\n", ++cout );while( !empty() ){ps = pop();printf( "%d %d\n", ps.u, ps.v );}printf( "\n" );}}return 0;
}

这篇关于UVA 10054的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---