#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】 解题报告+AC代码
poj2492 A Bug's Life并查集应用的扩展,希望可以给大家带来用处
POJ 1988 并查集。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
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
这份代码用C++实现了经典算法并查集,来源于poj题目1182
北大POJ2525-Text Formalization【TrieTree】 解题报告+AC代码+测试数据 http://hi.csdn.net/!s/XW4FQ3
并查集基础 acm 算法 poj oi 并查集基础.ppt
poj 1611 The Suspects 代码 并查集的应用
POJ1089 并查集可以解决 并查集加路径压缩
数据结构并查集的相关资料,包括几篇并查集的论文,还有POJ上面几道关于并查集的题目的源代码
poj 800+ 题目源代码,多年做题积累 包含各种类型经典题目
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
很好很强大的POJ分类 新手+进阶+题目完全分类 赶快下载
西北工业大学POJ试题C++答案代码+课程设计
北大POJ初级-简单搜索 解题报告+AC代码
北大POJ3009-Curling 2.0【DFS+Vector+回溯+剪枝】 解题报告+AC代码
NULL 博文链接:https://128kj.iteye.com/blog/1750462
北大POJ1207-The 3n + 1 problem 解题报告+AC代码
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
北大POJ1159-Palindrome 解题报告+AC代码