最新消息:点击查看大S的省钱秘笈

POJ 2513 Colored Sticks C语言版

POJ题解 Slyar 4254浏览 5评论

文章作者:姜南(Slyar) 文章来源:Slyar Home (www.slyar.com) 转载请注明,谢谢合作。

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的字符串,问能否将所有的木棍排成一排,使得每两根木棍衔接的地方颜色相同。

这题我一开始暴力做,很随意的就TLE了…看了Discuss发现要用什么”Trie”和”欧拉通路”,还要用到前几天学会的并查集…晕死,根本不知道什么是“Trie”和”欧拉通路”,遂Google了一下,得知“Trie”俗称字典树,具体内容完了发到博客上…欧拉通路完了也发博客上…本文发表2 weeks后应该可以搜索到…

对于知道以上概念者,可以看出本题就是将所有的颜色看做节点,连接两种颜色的木棍看做节点之间的连边,判断无向图中是否存在欧拉通路,判断条件是:

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

转载请注明:Slyar Home » POJ 2513 Colored Sticks C语言版

发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

网友最新评论 (5)

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