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

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

## 输入输出样例

`blue redred violetcyan blueblue magentamagenta cyan`

`Possible`

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