洛谷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;
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018-02-28 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录