程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> UVA 10054 The Necklace

UVA 10054 The Necklace

編輯:關於C++
10054 The Necklace
My little sister had a beautiful necklace made of colorful beads. Two successive beads in the necklace
shared a common color at their meeting point. The figure below shows a segment of the necklace:
But, alas! One day, the necklace was torn and the beads were all scattered over the floor. My sister
did her best to recollect all the beads from the floor, but she is not sure whether she was able to collect
all of them. Now, she has come to me for help. She wants to know whether it is possible to make a
necklace using all the beads she has in the same way her original necklace was made and if so in which
order the bids must be put.
Please help me write a program to solve the problem.
Input
The input contains T test cases. The first line of the input contains the integer T.
The first line of each test case contains an integer N (5 ≤ N ≤ 1000) giving the number of beads
my sister was able to collect. Each of the next N lines contains two integers describing the colors of a
bead. Colors are represented by integers ranging from 1 to 50.
Output
For each test case in the input first output the test case number as shown in the sample output. Then
if you apprehend that some beads may be lost just print the sentence “some beads may be lost”
on a line by itself. Otherwise, print N lines with a single bead description on each line. Each bead
description consists of two integers giving the colors of its two ends. For 1 ≤ i ≤ N 1, the second
integer on line i must be the same as the first integer on line i + 1. Additionally, the second integer on
line N must be equal to the first integer on line 1. Since there are many solutions, any one of them is
acceptable.
Print a blank line between two successive test cases.
Sample Input
2
5
1 2
2 3
3 4
4 5
5 6
5
2 1
2 2
3 4
3 1
2 4Universidad de Valladolid OJ: 10054 – The Necklace 2/2
Sample Output
Case #1
some beads may be lost
Case #2
2 1
1 3
3 4
4 2

2 2

題意:給你n條邊,要你判斷這些邊能不能組成歐拉回路,並輸出它的路徑

思路:歐拉回路的模板題

AC代碼:

 

#include
#include

int g[60][60],d[60],p[60];

int find(int x)
{
    if(x!=p[x])
        p[x]=find(p[x]);
    return p[x];
}

void dfs(int u)
{
    int v;
    for(v=1;v<=50;v++)
        if(g[u][v]){
        g[u][v]--;
        g[v][u]--;
        dfs(v);
        printf("%d %d\n",v,u);
    }
}

int main()
{
    int i,j,k,t;
    int cas=1;

   // freopen("in.cpp","r",stdin);
   // freopen("out.cpp","w",stdout);

    scanf("%d",&t);
    while(t--)
    {
        int n,u,v;
        scanf("%d",&n);
        memset(g,0,sizeof(g));
        memset(d,0,sizeof(d));
        for(i=1;i<=50;i++)
            p[i]=i;
        for(i=0;i

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved