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

2018-03-01 12:21:58来源:cnblogs.com作者:自为风月马前卒人点击

分享

题目描述

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

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

输入输出格式

输入格式:

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

输出格式:

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

输入输出样例

输入样例#1: 复制
blue redred violetcyan blueblue magentamagenta 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;}

最新文章

123

最新摄影

闪念基因

微信扫一扫

第七城市微信公众平台