题目大意：
给定一些木棒，木棒两端都涂上颜色，求是否能将木棒首尾相接，连成一条直线，要求不同木棒相连接的一端必须是同颜色的。
解题思路：
可以用图论中欧拉路的知识来解这道题，首先可以把木棒两端看成节点，把木棒看成边，这样相同的颜色就是同一个节点
问题便转化为：给定一个图，是否存在“一笔画”经过涂中每一点，每条边一次。
这样就是求图中是否存在欧拉路Euler-Path。
关于度数的判断方法：
节点的度用颜色出现次数来统计，如样例中，蓝色blue出现三次（不管是出度还是入度），那么blue结点的度就为3，同样地，我们也可以通过输入得到其他全部结点的度，于是，我们有：
Magenta=2
Blue=3
Red=2
Violet=1
Cyan=2
用一个一维数组就能记录了，然后分别模2，就能判断颜色结点的奇偶性
只要奇度数的结点数的个数=1或>=3，即使图连通，也一定不存在欧拉路径
Trie树+并查集+欧拉路径
#include<cstdio>
#include<cstdlib>
#define maxn 500010
typedef struct Trie{
int pos;
struct Trie *next[];
}Trie,*trie;
trie root;
int k=,fa[maxn],d[maxn];
void Init(trie &p)
{
p=(trie)malloc(sizeof(Trie));
for(int i=;i<;i++) p->next[i]=NULL;
p->pos=;
}//建Trie树,返回单词编号
int Build(trie &p,char *s,int depth)
{
if(!s[depth]){
if(p->pos) return p->pos;
p->pos=++k;
fa[k]=k,d[k]=;//初始化祖先为自身,度数为0
return k;
}//q不能定义为全局变量
trie q=p->next[s[depth]-'a'];
if(q==NULL){
Init(q);
p->next[s[depth]-'a']=q;
}
return Build(q,s,depth+);
}
int Findset(int x)
{
if(fa[x]==x) return x;
return fa[x]=Findset(fa[x]);
}
void Union(int u,int v)
{
int x=Findset(u);
int y=Findset(v);
if(x!=y) fa[x]=y;
}
int main()
{
Init(root);
char s[],t[];
while(scanf("%s%s",s,t)!=EOF){
int x=Build(root,s,);
int y=Build(root,t,);
Union(x,y);
d[x]++,d[y]++;
}
int scc=,odd=;
for(int i=;i<=k;i++){
if(fa[i]==i) scc++;//不连通
if(d[i]&) odd++;//奇度节点
}
if(scc>||odd>) puts("Impossible");
else puts("Possible");
return ;
}
离散化+并查集+欧拉路径
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 500010
using namespace std;
int num[maxn],fa[maxn];
int idxc=,idxw=,cnt; struct Wood{
char left[],right[];
}wood[maxn/];
struct Node{
char col[];
bool operator<(const Node tmp)const{
if(strcmp(col,tmp.col)<=)
return true;
return false;
}
}node[maxn];
//二分查找颜色对应离散的编号
int Binary_Search(char *col){
int l=,r=cnt+;
while(r-l>){
int mid=(r+l)/;
if(strcmp(node[mid].col,col)<=) l=mid;
else r=mid;
}
return l;
}
int Findset(int x)
{
if(fa[x]!=x)
fa[x]=Findset(fa[x]);
return fa[x];
} int main()
{
char s1[],s2[];
while(scanf("%s%s",wood[idxw].left,wood[idxw].right)!=EOF){
strcpy(node[idxc++].col,wood[idxw].left);
strcpy(node[idxc++].col,wood[idxw].right);
idxw++;
}
sort(node+,node+idxc);
memset(num,,sizeof(num));
num[]++,cnt=;
for(int i=;i<idxc;i++){//进行离散处理,同时统计每种颜色出现的个数
if(strcmp(node[i].col,node[i-].col)!=){
strcpy(node[++cnt].col,node[i].col);
num[cnt]++;//颜色不同保留下来
}
else num[cnt]++;//颜色相同直接计数
}
for(int i=;i<maxn;i++) fa[i]=i;
for(int i=;i<idxw;i++){
int u=Binary_Search(wood[i].left);
int v=Binary_Search(wood[i].right);
int x=Findset(u),y=Findset(v);
if(x!=y) fa[x]=y;
}
int scc=,odd=;//cnt是节点编号,也是节点个数
for(int i=;i<=cnt;i++){
if(fa[i]==i) scc++;
if(num[i]%) odd++;
}
if(idxw==||(scc==&&(odd==||odd==))) printf("Possible\n");
else printf("Impossible\n");
}