洛谷P1333 瑞瑞的木棍(欧拉回路)

题目描述

瑞瑞有一堆的玩具木棍,每根木棍的两端分别被染上了某种颜色,现在他突然有了一个想法,想要把这些木棍连在一起拼成一条线,并且使得木棍与木棍相接触的两端颜色都是相同的,给出每根木棍两端的颜色,请问是否存在满足要求的排列方式。

例如,如果只有2根木棍,第一根两端的颜色分别为red,blue,第二根两端的颜色分别为red,yellow,那么blue---red|red----yellow便是一种满足要求的排列方式。

输入输出格式

输入格式:

输入有若干行,每行包括两个单词,表示一根木棍两端的颜色,单词由小写字母组成,且单词长度不会超过10个字母,最多有250000根木棍。

输出格式:

如果木棒能够按要求排列,输出Possible,否则输出Impossible

输入输出样例

输入样例#1: 

blue red
red violet
cyan blue
blue magenta
magenta cyan

输出样例#1:

Possible

我们把相同颜色的点看做一个节点

那么这个题就是判断是否含有欧拉路(欧拉路径)

欧拉路的判断基本都是DFS

但其实并查集也可以做

设x为成功合并的次数,n为点数

则整张图含欧拉路当且仅当x>=n-1且奇度数点为0或2

顺便提一下

pbds真是个好东西

#include<cstdio>
#include<cstring>
#include<map>
#include<iostream>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
const int MAXN=1e6+10;
gp_hash_table<string,int>mp;
int tot=0,fa[MAXN],inder[MAXN];
int find(int x)
{
    if(fa[x]==x) return fa[x];
    else return fa[x]=find(fa[x]);
}
int unionn(int x,int y)
{
    inder[x]++;inder[y]++;
    int fx=find(x),fy=find(y);
    if(fx==fy) return 0;
    fa[fx]=fy; return 1;
}
int main()
{
    ios::sync_with_stdio(false); 
    for(int i=1;i<=250001;i++) fa[i]=i;
    string a,b;
    int ans=0;
    while(cin>>a>>b)
    {
        int posa=mp[a]?mp[a]:mp[a]=++tot;
        int posb=mp[b]?mp[b]:mp[b]=++tot;
        ans+=unionn(posa,posb);    
    }
    if(ans<tot-1) {printf("Impossible\n");return 0;}
    int attack=0;
    for(int i=1;i<=tot;i++)
        if(inder[i]&1) attack++; 
    if(attack>2) {printf("Impossible\n");return 0;}
    printf("Possible\n");
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数说工作室

【SAS Says】基础篇:描述性分析(下)

好吧,这一节是留给处女座的,主要说如何用proc tabulate和proc report产生一个更加耐看的报告。有时候print、means和freq产生的报...

5785
来自专栏web编程技术分享

用canvas制作彩虹球喷枪(js面向对象小案例)

4186
来自专栏每日一篇技术文章

OpenGL ES _ 着色器_ 顶点着色器详解

提醒广大网友,当你看到这篇文章的时候,以后写的关于OpenGL 更多的便是代码实战了!

8531
来自专栏数据处理

proc-tabulate

1172
来自专栏数据结构与算法

1225 八数码难题

1225 八数码难题  时间限制: 1 s  空间限制: 128000 KB  题目等级 : 钻石 Diamond 题解  查看运行结果 题目描述 Descri...

2864
来自专栏数据结构与算法

BZOJ4773: 负环(倍增Floyd)

一个很显然的思路(然而我想不到是用\(f[k][i][j]\)表示从\(i\)号点出发,走\(k\)步到\(j\)的最小值

1193
来自专栏数据结构与算法

17:文字排版

17:文字排版 查看 提交 统计 提问 总时间限制: 1000ms 内存限制: 65536kB描述 给一段英文短文,单词之间以空格分隔(每个单词包括其前后紧邻...

3107
来自专栏Petrichor的专栏

leetcode: 90. Subsets II

1113
来自专栏软件开发 -- 分享 互助 成长

函数依赖集闭包、属性集闭包、超键、候选键和最小函数依赖集的求法。

函数依赖集的闭包 F:FD的集合称为函数依赖集。 F闭包:由F中的所有FD可以推导出所有FD的集合,记为F+。 例1,对于关系模式R(ABC),F={A→B,B...

4305
来自专栏尾尾部落

[LeetCode]Palindrome Number回文

链接:https://leetcode.com/problems/palindrome-number/#/description 难度:Easy 题目:De...

1252

扫码关注云+社区

领取腾讯云代金券