一 问题描述
给你一堆木棒。每根棒的每个端点都用一些颜色着色。是否可以将棒对齐成直线,使得接触的端点的颜色具有相同的颜色?
二 输入和输出
1 输入
输入是一系列行,每行包含两个单词,由空格分隔,给出一个木棒的端点颜色。单词是一个不超过 10 个字符的小写字母序列。不超过 250000 根木棒。
2 输出
如果木棒可以以所需方式对齐,则输出单行表示可能,否则输出不可能。
三 输入和输出样例
1 输入样例
blue red
red violet
cyan blue
blue magenta
magenta cyan
2 输出样例
Possible
四 分析和设计
1 分析
本问题可以把木棒的两端看成点,把木棒看成边,相同的颜色为同一个节点。那么问题转化为“一笔画”,即欧拉通路问题,经过每个顶点一次且只有一次,行遍所有的边。
由图论知识可知,无向图存在欧拉通路的充要条件为:
a 图是连通的。
b 无奇度节点或恰好有两个奇度节点(度为奇数的节点)。
连通性可以采用并查集处理,节点的度可以采用字典树进行统计。
解决方案:字典树 + 并查集 + 欧拉通路。
2 设计
a 将输入数据插入到字典树中,并累加颜色节点的度,合并集合。
b 求 1 号节点的集合号(如果连通,则所有节点的集合号相同)。
c 统计奇度节点的个数,如果大于2,则不可能存在欧拉通路,输出不可能。
d 如果集合号不等,则说明不连通,输出不可能。
e 如果没有奇度节点或恰好两个奇度节点,输出可能。
五 代码
package com.platform.modules.alg.alglib.poj2513;public class Poj2513 {private int maxn = 500010;private int maxz = 26; // 不同字符个数,小写字母 26int trie[][] = new int[maxn][maxz];boolean end[];int tot; // 字符串数,下标int color = 0; //颜色编号指针,最终为颜色总个数int degree[];int col[]; // 结点的度数,颜色号int fa[]; // 祖先,即集合号public String output = "";void Init() {end = new boolean[maxn]; // 标记结束degree = new int[maxn];col = new int[maxn];fa = new int[maxn];tot = 1;}// 找祖先int Find(int x) {if (fa[x] != x)fa[x] = Find(fa[x]);return fa[x];}// 合并集合void Union(int a, int b) {int pa = Find(a);int pb = Find(b);fa[pb] = pa;}int Insert(String s) {//将字符串 s 插入到字典树中int p = 1;for (int i = 0; i < s.length(); i++) {int ch = s.charAt(i) - 'a'; // 转换成数字if (trie[p][ch] == 0)trie[p][ch] = ++tot; // 记录下标p = trie[p][ch];}if (end[p]) // 颜色单词已存在return col[p]; //返回其颜色号else { // 否则创建单词end[p] = true;col[p] = ++color;return col[p];}}public String cal(String input) {Init();for (int i = 1; i < maxn; i++)fa[i] = i;String[] line = input.split("\n");for (int k = 0; k < line.length; k++) {String[] colors = line[0].split(" ");int i = Insert(colors[0]);int j = Insert(colors[1]); // 得到 a、b 颜色的编号degree[i]++;degree[j]++;// 记录 a、b 颜色出现的次数(总度数)Union(i, j);}int s = Find(1); // 若图为连通图,则 s 为所有结点的祖先int num = 0; // 度数为奇数的结点个数for (int i = 1; i <= color; i++) {if (degree[i] % 2 == 1)num++;if (num > 2 || Find(i) != s) { // 存在多个祖先,图为森林,不连通output = "Impossible\n";return output;}}if (num == 0 || num == 2) // 没有奇度顶点或恰好两个奇度顶点output = "Possible\n";elseoutput = "Impossible\n";return output;}
}
六 测试