洛谷P1333 瑞瑞的木棍

題目描述

瑞瑞有一堆的玩具木棍，每根木棍的兩端分別被染上了某種顏色，現在他突然有了一個想法，想要把這些木棍連在一起拼成一條線，並且使得木棍與木棍相接觸的兩端顏色都是相同的，給出每根木棍兩端的顏色，請問是否存在滿足要求的排列方式。

例如，如果只有2根木棍，第一根兩端的顏色分別為red,blue，第二根兩端的顏色分別為red,yellow，那麼blue---red|red----yellow便是一種滿足要求的排列方式。

輸入輸出格式

輸入格式：

輸入有若幹行，每行包括兩個單詞，表示一根木棍兩端的顏色，單詞由小寫字母組成，且單詞長度不會超過10個字母，最多有250000根木棍。

輸出格式：

如果木棒能夠按要求排列，輸出Possible，否則輸出Impossible

輸入輸出樣例

blue red
red violet
cyan blue
blue magenta
magenta cyan

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;
}