# POJ 2513 Colored Sticks C语言版

POJ题解 4799浏览

Trie树+并查集+欧拉通路

Description

You are given a bunch of wooden sticks. Each endpoint of each stick is colored with some color. Is it possible to align the sticks in a straight line such that the colors of the endpoints that touch are of the same color?

Input

Input is a sequence of lines, each line contains two words, separated by spaces, giving the colors of the endpoints of one stick. A word is a sequence of lowercase letters no longer than 10 characters. There is no more than 250000 sticks.

Output

If the sticks can be aligned in the desired way, output a single line saying Possible, otherwise output Impossible.

Sample Input

blue red
red violet
cyan blue
blue magenta
magenta cyan

Sample Output

Possible

Slyar:说下题目大意，给出n根木棍，每根木棍两端都有颜色，颜色为小于10的字符串，问能否将所有的木棍排成一排，使得每两根木棍衔接的地方颜色相同。

1、有且只有两个度为奇数的节点

2、图是连通的

eg. blue (magenta magenta) (cyan cyan) (blue blue) (red red) violet

```/*
PKU 2513
Slyar
//www.slyar.com/
*/

#include
#include

#define MAX 500001

/* father[x]表示x的父节点 */
int father[MAX];
/* rank[x]表示x的秩 */
int rank[MAX];
/* degree记录节点的度 */
int degree[MAX];
/* 记录字典树有效节点个数 */
int num = 0;

/* 定义字典树节点类型 */
typedef struct node
{
int key;
struct node *next[26];
}trie;

/* 创建根节点 */
trie *root;

/* 创建新节点 */
trie* New()
{
int i;
trie *p;
p = (trie*) malloc(sizeof(trie));
/* 初始化节点为未访问 */
p->key = -1;
/* 初始化孩子指针 */
for (i = 0; i < 26; i++)
{
p->next[i] = NULL;
}
return p;
}

/* 初始化 */
void Make_Set(int x)
{
father[x] = x;
rank[x] = 0;
degree[x] = 0;
}

/* 查找x元素所在的集合,回溯时压缩路径 */
int Find_Set(int x)
{
if (x != father[x])
{
father[x] = Find_Set(father[x]);
}
return father[x];
}

/* 合并x,y所在的集合 */
void Union(int x, int y)
{

if (x == y) return;
if (rank[x] > rank[y])
{
father[y] = x;
}
else
{
if (rank[x] == rank[y])
{
rank[y]++;
}
father[x] = y;
}
}

/* 向以root为根的树中插入字符串s */
int Insert(trie *root, char *s)
{
int i;
trie *p = root;
for (i = 0; s[i] != '\0'; i++)
{
/* 节点若不存在则创建 */
if (p->next[s[i] - 'a'] == NULL)
{
p->next[s[i] - 'a'] = New();
}
/* 向下一层移动 */
p = p->next[s[i] - 'a'];
}
/* 得到并返回颜色节点序号 */
if (p->key == -1)
{
p->key = ++num;
}
return p->key;
}

/* 主函数 */
int main()
{
int i, x, y, sum;
char s1[11], s2[11];

/* 初始化集合 */
for (i = 0; i < MAX; i++)
{
Make_Set(i);
}

/* 初始化根节点 */
root = New();

/* 处理字符串 */
while(scanf("%s%s", s1, s2) != EOF)
{
/* 插入颜色，得到颜色节点序号 */
x = Insert(root, s1);
y = Insert(root, s2);
/* 更新颜色节点的度 */
degree[x]++;
degree[y]++;
/* 合并两根木棍 */
Union(Find_Set(x), Find_Set(y));
}

sum = 0;

/* 求度为奇数的点的个数 */
for (i = 1; i < num; i++)
{
if(degree[i] % 2) sum++;
}

/* 若度大于2则肯定不可能 */
if (sum > 2)
{
printf("Impossible\n");
}
/* 否则考察图是否连通 */
else
{
/* 考察所有的点是否在一个集合 */
for (i = 2; i < num; i++)
{
if (Find_Set(i) != Find_Set(1))
{
printf("Impossible\n");
return 0;
}
}
printf("Possible\n");
}

//system("pause");
return 0;
}
```

### 网友最新评论 (5)

1. ORZ!!膜拜楼主！！！
菜鸟一号10年前 (2011-08-11)回复
2. QRZ!!楼主强大！！
匿名10年前 (2011-08-10)回复
3. @Slyar 努力的小盆友，粉有前途。。。
Felix02112年前 (2009-06-12)回复
4. @Felix021, 呃...在学习算法...
Slyar12年前 (2009-06-12)回复
5. Slyar童鞋最近狂刷POJ阿。
Felix02112年前 (2009-06-12)回复