UVa 10054 : The Necklace 【欧拉回路】

UVa 10054 : The Necklace 【欧拉回路】

大家好,又见面了,我是全栈君。

题目链接

题目大意:我的妹妹有一串由各种颜色组成的项链。 项链中两个连续珠子的接头处共享同一个颜色。 如上图, 第一个珠子是green+red, 那么接这个珠子的必须以red开头,如图的red+white.
噢!天啊! 一天, 项链项链被扯断了,珠子掉落了一地。我的妹妹竭尽全力的把珠子一个个捡起来, 但是她不确定是否全部捡回来了。 现在,她叫我帮忙。 
她想知道是否可能把这些珠子全部连接起来, 连接的方法和项链原来的方法一样。
请帮我写一个程序解决这个问题。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

const int N=60;

int n;
int T,kase=0;
int p[N];
int Find(int x)
{
    if(p[x]==-1) return x;
    return x==p[x]? x:p[x]=Find(p[x]);
}
void Union(int x,int y)
{
    x=Find(x),y=Find(y);
    p[x]=y;
}

int num[N];
int G[N][N];

void Traverse(int u)
{
    for(int v=1;v<=50;v++)
        if(G[u][v]>0)
        {
            G[u][v]--,G[v][u]--;
            Traverse(v);
            printf("%d %d\n",v,u);    //不可以顺序打印 
        }
}

void solve()
{
    if(kase>0) puts("");
    printf("Case #%d\n",++kase);
    int pp=-1;
    for(int i=1;i<=50;i++)
    {
        if(num[i]==0) continue;
        if(num[i]&1)     //存在奇度数结点 
        {
            puts("some beads may be lost");
            return ;
        }
        if(pp==-1)
        {
            pp=Find(i);
            continue;
        }
        if(pp!=Find(i))    //不联通 
        {
            puts("some beads may be lost");
            return ;
        }
    }
    Traverse(pp);
}

void init()
{
    memset(p,-1,sizeof(p));
    memset(num,0,sizeof(num));
    memset(G,0,sizeof(G));
}

int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        init();
        for(int i=0;i<n;i++)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            num[u]++,num[v]++;
            G[u][v]++,G[v][u]++;    //无向图 
            Union(u,v);
        }
        solve();
    }
}

 

转载于:https://www.cnblogs.com/Just–Do–It/p/7448932.html

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请联系我们举报,一经查实,本站将立刻删除。

发布者:全栈程序员-站长,转载请注明出处:https://javaforall.net/108202.html原文链接:https://javaforall.net

(0)
全栈程序员-站长的头像全栈程序员-站长


相关推荐

  • Tarjan_com.pakdata.QuranMajeed

    Tarjan_com.pakdata.QuranMajeedTarjanTarjan是一种求有向图强联通分量的算法,是用dfs实现以及时间戳标记访问最短时间的.Tarjan算法中每个点都需要扩展边,为了存储方便,推荐使用邻接表.Tarjan算法的优势在于其灵活性,基础代码可以直接适用于多数情况.常见于dfs序.

    2022年10月27日
    0
  • [C语言]背包问题「建议收藏」

    [C语言]背包问题「建议收藏」0-1背包问题 参考:http://blog.csdn.net/liwenjia1981/article/details/5725579http://blog.csdn.net/dapengbusi/article/details/7463968动态规划解法借个图助于理解从背包容量为0开始,1号物品先试,0,1,2,的容量都不能放.所以置0,背包容量为3则里面放4

    2022年7月14日
    13
  • VS2010 编译 SpiderMonkey 1.8.5 静态库版本[通俗易懂]

    VS2010 编译 SpiderMonkey 1.8.5 静态库版本[通俗易懂]大家好,前段时间看到VC驿站上面会员发布了一篇文章《Windows系统编译制作SpiderMonkey最新版mozjs-31.2.0版本》,地址为:http://www.cctry.com/thread-250698-1-1.html过程写的很详细,使用的也是目前来说SpiderMonkey的最新版本31.2.0,不过我之前用的一直是1.8.5版本,用老的版本编译出来的SpiderMonkey

    2022年10月16日
    0
  • 俞敏洪沉默,新东方落泪

    俞敏洪沉默,新东方落泪据传,早些年以新东方三位创始人创业为主线故事,风靡一时的电影《中国合伙人》开拍前,剧组曾向电影男主角的原型人物俞敏洪,提出了友好交流的请求。俞敏洪提出最大的意见是:可不可以别把我拍得这么“土鳖”?几十年来,号称农村出身的寒门子弟俞敏洪,其身份发生了重大变化。在公开场合里,他对自己的身世表露出深深的自卑。另一方面,他又被誉为中国留学教父,俨然成为一个农村“凤凰男”逆袭成精英阶级的典型代表。当然,俞敏洪还是新东方的创始人,中国商业洪流里响当当的传奇。“我吃一碗兰州拉面都很开心”。可就是这样一个人,对财

    2022年9月13日
    0
  • vector-list-deque

    vector-list-deque

    2021年8月18日
    50
  • app hybrid框架_混合式app

    app hybrid框架_混合式app几种APP开发模式概述当前的APP开发模式注意有以下四大类型:NativeApp 即传统的原生APP开发模式,Android基于Java语言,底层调用Google的API;iOS基于OC或者Swift语言,底层调用App官方提供的API。体验最后。 WebApp 即移动端的网站,将页面部署在服务器上,然后用户使用各大浏览器访问。一般泛指SPA(SinglePa…

    2022年9月2日
    3

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

关注全栈程序员社区公众号