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

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

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

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • php navigator,navigator对象

    php navigator,navigator对象navigator对象appName:浏览器软件名称,主要用来判断客户使用的是什么核心的浏览器。如果是IE浏览器的话,返回值为:MicrosoftInternetExplorer如果是Firefox浏览器的话,返回值为:NetscapeappVersion:浏览器软件的核心版本号。systemLanguage:系统语言userLanguage:用户语言platform:平台HTML>ph…

  • opencv 滤波 方框滤波 均值滤波 高斯滤波 中值滤波 双边滤波[通俗易懂]

    文章目录一.线性滤波1.1.方框滤波demo1.2.均值滤波demo1.3.高斯滤波demo二.非线性滤波2.1.中值滤波demo2.2.双边滤波demo结构体参考一.线性滤波1.1.方框滤波方框滤波是所有滤波器中最简单的一种滤波方式。每一个输出像素的是内核邻域像素值的平均值得到。通用的滤波kernel如下:这里是一个长宽分别为Kwidth和Kheight的窗口函数,在此区域内邻域中像素值叠加求平均即可求出位于kernel中心点像素的像素值。/**@brief使用框过滤

  • GMT、UTC、PDT 时间简介

    GMT、UTC、PDT 时间简介GMTGMT是GreenwichMeanTime的缩写,译为中文为“格林威治标准时间”或“格林尼治标准时间”,直译的话,可译为“格林威治平时”或“格林尼治平时”。这里的格林威治位于英国伦敦东

  • Windows端口被占用_windows如何打开端口

    Windows端口被占用_windows如何打开端口电脑系统为Windows10一以管理员身份打开命令行窗口【Win+R】:使用快捷键打开“运行”窗口输入【cmd】,点击确定,打开“命令”窗口二查看被占用端口对应的PID比如在开发时,系统提示你1080已被占用,我们首先要做的就是找到1080端口对应的PID。在命令行中输入命令:netstat-aon|findstr”1080″回车执行命令后,最后一位数字就是被占用窗口的PID。我这里对应的是16996和18912。三查看指定PID的进程在命令行中输入命令:ta.

  • 医学图形图像处理(医学影像和医学图像处理)

    文章目录1图像和数字图像1图像和数字图像  数字图像:被定义为一个二维函数,f(x,y),其中x,y代表空间坐标,f代表点(x,y)处的强度或灰度级。和普通的笛卡尔坐标系有区别,在计算机中坐标系左上角为原点:  图像数字化:图像进入计算机后,对图像进行数字化(映射)。数字图像三要素:  (1)像素:大小决定了图像存储、显示的清晰度;  (2)灰度值:通常为0-255,因为在计算机中通常用一个字节来表示一个像素,即28。  (3)坐标  图像存储在计算机中会丢失信息,因为是从一个连续的

  • Kafka简明教程「建议收藏」

    Kafka简明教程「建议收藏」作者:柳树之www.jianshu.com/p/7b77723d4f96Kafka是啥?用Kafka官方的话来说就是:Kafkaisusedforbuildingreal-timedatapipelinesandstreamingapps.Itishorizontallyscalable,fault-tolerant,wickedfast,an…

    2022年10月17日

发表回复

您的电子邮箱地址不会被公开。

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