POJ2513_Colored Sticks_KEY

题目传送门

题目大意：给你若干根木棍，每根木棍有前后两种颜色，连接两根木棍需要前后颜色相同，求能否将所有木棍连接在一起。

Solution：

不要将木棍看成点，将颜色看成点。

其实就是求是否存在欧拉路径。

有欧拉路径要满足两个条件：

　　图是连通图。

　　没有或只有两个入度为奇数的点。

判断连通性用并查集。

枚举每个点判断入度就好了。

code：

#include <cstdio>

#include <cstring>

#include <iostream>

using namespace std;

struct trie{

    int tr[][],v[],cnt,tot;

    trie(){memset(tr,,sizeof tr),memset(v,,sizeof v),cnt=tot=;}

    int add(char *a)

    {

        int len=strlen(a),now=;

            for(int i=;i<len;i++){

                if(!tr[now][a[i]-'a'])tr[now][a[i]-'a']=++cnt;

                now=tr[now][a[i]-'a'];

            }

        if(!v[now])v[now]=++tot;

        return v[now];

    }

}T;

char S1[],S2[];

int into[],fa[];

int getf(int x){return x==fa[x]?x:fa[x]=getf(fa[x]);}

int main()

{

//    freopen("x.txt","r",stdin);

    for(int i=;i<=;i++)fa[i]=i;

    while(cin>>S1>>S2){

        int k1=T.add(S1),k2=T.add(S2);

        into[k1]++,into[k2]++;

        fa[getf(k1)]=getf(k2);

    }

    int ans=;

    for(int i=;i<=T.tot;i++)

        if(fa[getf(i)]==i)ans++;

    if(ans>)return puts("Impossible"),;

    ans=;

    for(int i=;i<=T.tot;i++){

        if(into[i]&)ans++;

    }

    if(!ans||ans==)puts("Possible");

    else puts("Impossible");

    return ;

}