`
kenby
  • 浏览: 724669 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

poj 2513 trie + 并查集 + 欧拉通路

阅读更多

 

#include <stdio.h>
#include <string.h>

//#define DEBUG

#ifdef DEBUG
#define debug(...) printf( __VA_ARGS__) 
#else
#define debug(...)
#endif

#define M 530001
#define N 500001

struct trie_node {
	int color_id; 			/* 叶子节点存储颜色编号,从1开始 */
	int child[26];			/* 分支节点,静态链表表示 */
};
struct trie_node trie_tree[M];	/* trie树的静态链表表示法,trie_tree[0]是树根 */
int  current;					/* Trie树当前使用了多少个节点 */

int	 parent[N];					/* 并查集树形表示,parent[u] = r,若r > 0,u的
								   父亲为r, 若r < 0, 则u是根节点,其高度为-r */
int  degree[N];
int  n;							/*顶点个数, 即有多少种颜色 */

/* 把单词插入Trie树,如果单词已存在直接返回颜色编号,
 * 不存在则插入,同时返回新生成的颜色编号 
 */
int insert(char *color)
{
	char				*p;
	struct trie_node 	*node;
	int					new_node;

	node = trie_tree;
	//沿着树根一直往下插
	for (p = color; *p != '\0'; p++) {
		debug("开始插入 %c...\n", *p);
		if (node->child[*p-'a'] == 0) {
			debug("没有%c, 新建节点\n", *p);
			node->child[*p-'a'] = current++;
		}
		else {
			debug("存在%c\n", *p);
		}
		node = trie_tree + node->child[*p-'a'];
	}
	//到达记录统计单词次数的节点
	if (node->color_id == 0) {
		node->color_id = ++n;
	} 
	debug("%s插入完成,其编号为%d\n", color, node->color_id);
	return node->color_id;
}

/* 找i的根节点 */
int find(int i)
{
	for(; parent[i] > 0; i = parent[i]) ;
	return i;
}

void merge(int x,int y)
{
	int		px, py;

	px = find(x);
	py = find(y);
	if (px == py) return;
	debug("%d的树根为%d,树高=%d,%d的树根为%d, 树高=%d\n", x, px, -parent[px], y, py, -parent[py]);
	if (parent[px] < parent[py]) {	/* x所在的树比y所在的树要高 */
		parent[py] = px;
		debug("合并后树根为%d, 高度=%d\n", px, -parent[px]);
	}
	else if (parent[px] > parent[py]) { /* x所在的树比y所在的树要矮 */
		parent[px] = py;
		debug("合并后树根为%d, 高度=%d\n", py, -parent[py]);
	}
	else {
		parent[py] = px;
		parent[px]--;	/* 树的高度加1 */
		debug("合并后树根为%d, 高度=%d\n", px, -parent[px]);
	}
}

int main()
{
	char	color1[11], color2[11];
	int 	u, v, subgraph, count;

	current = 1;
	n = 0;
	memset(parent, -1, sizeof(parent));
	memset(degree, 0, sizeof(degree));

	while (scanf("%s %s", color1, color2) != EOF) {
		u = insert(color1);
		v = insert(color2);
		degree[u]++;
		degree[v]++;
		merge(u, v);
	}

	//空数据打印Possible, 否则Wrong Answer
	if (n == 0) {
		printf("Possible\n");
		return 0;
	}

	//计算奇数度顶点的个数
	count = 0;
	for (u = 1; u <= n; u++) {
		if (degree[u]%2 != 0) {
			if(++count > 2) break;
		}
	}
	debug("奇数度的顶点个数为%d\n", count);

	/* 计算并查集有几个分支,只有一个分支,说明图是连通的, 
	 * 如果有两个或两个以上的分支,则图不是连通的
	 */
	subgraph = 0;
	if (count == 0 || count == 2) {
		for (u = 1; u <= n; u++) {
			/* parent[u] < 0说明u是树根,有多少树根,并查集就有多少个分支 */
			if (parent[u] < 0) { 
				if (++subgraph > 1) {
					break;
				}
			}
		}
		if (subgraph == 1) {
			printf("Possible\n");
			return 0;
		}
	}
	printf("Impossible\n");
	return 0;
}
分享到:
评论

相关推荐

    POJ2513-Colored Sticks【TrieTree+MergeSet+EulerPath】

    【标题】"POJ2513-Colored Sticks【TrieTree+MergeSet+EulerPath】"涉及的是一道编程竞赛题目,主要考察参赛者的数据结构与算法应用能力,特别是Trie树(字典树)、并查集(MergeSet)以及欧拉路径(Euler Path)这...

    poj2492并查集应用的扩展

    poj2492 A Bug's Life并查集应用的扩展,希望可以给大家带来用处

    POJ 1988 简单并查集,

    根据给定的信息,本文将详细解释“POJ 1988 简单并查集”中的核心知识点,包括并查集的基本概念、代码实现以及在本题中的具体应用。 ### 并查集基本概念 并查集是一种用于处理一些不交集的合并及查询问题的数据...

    POJ 新手题目+部分难题 基本数论+图论+组合数学

    2505 2521 2538 2546 2551 2590 2593 2601 2665 2680 2739 2752 2761 2762 2777 2800 2891 2893 2992 3030 3041 3132 3159 3187 3204 3270 3277 3281 3297 3321 3414 3436 3461 3650 3663 3664 3672 3740

    数据结构--并查集(Union-Find Sets)

    此外,它也是算法竞赛中的常见题目类型,例如POJ等在线编程平台上的题目就经常涉及并查集的使用。 综上所述,并查集是一种非常实用的数据结构,它在处理集合的连接与查找问题时具有高效性和灵活性,对于理解和掌握...

    poj题目分类

    * 并查集的高级应用:例如 poj1703、poj2492。 * KMP 算法:例如 poj1961、poj2406。 4. 搜索: * 最优化剪枝和可行性剪枝。 * 搜索的技巧和优化:例如 poj3411、poj1724。 * 记忆化搜索:例如 poj3373、poj...

    并查集问题

    1. poj2524.cpp:这是一个POJ(Problem Setter's Online Judge)的编程题目,通常涉及到特定的算法问题,可能需要利用并查集解决连通性或路径查找问题。 2. hdoj1233最小生成树,克鲁斯卡尔.cpp:最小生成树是图论...

    POJ2525-Text Formalization【TrieTree】

    《POJ2525-Text Formalization:深入解析TrieTree》 在计算机科学的世界里,算法和数据结构是解决问题的关键。今天我们要探讨的是一个名为"POJ2525-Text Formalization"的问题,它涉及到一种高效的数据结构——Trie...

    并查集C++实现

    这份代码用C++实现了经典算法并查集,来源于poj题目1182

    ACM常用算法及其相应的练习题.docx

    * 简单并查集的应用 * 哈希表和二分查找等高效查找法 + poj3349, poj3274, poj2151, poj1840, poj2002, poj2503 * 哈夫曼树:poj3253 * 堆 * Trie树:静态建树、动态建树 + poj2513 四、简单搜索 * 深度优先搜索...

    POJ算法题目分类

    数据结构是指解决问题的数据结构,包括串、排序、简单并查集、哈希表和二分查找等高效查找法、哈夫曼树、堆、trie 树等。 * 串:串是指解决问题的基本数据结构,如 poj1035、poj3080、poj1936。 * 排序:排序是指...

    1089_bingchaji.rar_1089_bingchaji.rar _并查集

    在给定的标题“1089_bingchaji.rar_1089_bingchaji.rar _并查集”和描述“POJ1089 并查集可以解决 并查集加路径压缩”中,我们可以看到这是一个关于使用并查集解决特定问题的案例,可能来自于编程竞赛或练习。...

    并查集(Union Find set)基础

    并查集基础 acm 算法 poj oi 并查集基础.ppt

    并查集总结

    以POJ 1988为例,这是一个经典的并查集应用题,题目要求计算每个木箱上面还有多少木箱。通过并查集的查找和合并操作,结合路径压缩,可以有效地解决这一问题。 ```cpp #include #include void unionu(int x, int...

    poj 1611 The Suspects 代码

    poj 1611 The Suspects 代码 并查集的应用

    Trie树题解1

    在题目描述中提到的POJ1056、POJ1204、POJ2001、POJ2418、POJ2503、POJ2513和POJ1816等题目中,Trie树都起到了关键作用。 1. POJ1056 - 该题要求判断给定的二进制序列集合是否合法,即没有一个序列是另一个序列的...

    poj 800+ 题目源代码,多年做题积累

    《POJ 800+题目源代码:多年编程经验的结晶》 在编程的世界里,POJ(Programming Online Judge)是一个备受程序员喜爱的在线评测系统,它提供了大量的算法题目供用户挑战,以提升编程技能和算法理解能力。这份"poj ...

    POJ1011-Sticks

    一种常见的方法是使用深度优先搜索(DFS)或广度优先搜索(BFS)来构建线段之间的连接,并通过并查集(Disjoint Set)数据结构来判断是否存在不相交的集合。 1. **数据结构**:首先,我们需要用数组或者链表存储...

    poj训练计划.doc

    - 并查集的高级应用:如`poj1703, poj2492`。 - **搜索** - 最优化剪枝和可行性剪枝:如`poj3411, poj1724`。 - **动态规划** - 复杂的动态规划:如`poj1191, poj1054`。 - 记录状态的动态规划:如`poj3254, ...

    POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类

    - **解释**:并查集是一种用于处理集合合并及查询操作的数据结构。 #### 2. 特殊优化技巧 - **例题**:poj3393, poj1472, poj3371, poj1027, poj2706 - **解释**:特殊优化技巧通常涉及特定问题的优化算法,如位...

Global site tag (gtag.js) - Google Analytics