题目大意:给定一捆木棒,每根木棒的每个端点涂有某种颜色。问:是否能将这些棒子首位项链,排成一条直线,且相邻两根棍子的连接处的颜色一样。
解题思路:此题是一道典型的判断欧拉回路或欧拉通路的问题,以木棍的端点颜色为顶点。方法是:先用并查集判断图是否连通,然后统计奇度顶点的个数sumj , 如果 sumj == 0 , 则图中存在欧拉回路 ;如果 sumj == 2 , 则图中存在欧拉通路 ; 如果 sumj > 2 ,则图中不存在欧拉通路。但是此题的关键是如何给端点颜色编号,一开始,我用map映射,结果TLE,所以,我就用到了Trie 树。
Ps:此题有坑!!当没有输入时,应当输出 Possible 。。
具体请看代码:
#include<iostream> #include<cstring> #include<string> #include<cstdio> #include<cmath> #include<algorithm> #include<queue> using namespace std ; const int MAXN = 3e6; int set[MAXN] ; char s1[100] ; char s2[100] ; int cnt ; // 给端点编号 int d[MAXN] ; // 统计每个顶点的度 struct Tnode { int du ; int xu ; Tnode *next[26] ; Tnode() { du = 0 ; xu = 0 ; memset(next , 0 ,sizeof(next)) ; } } ; int find(int x) // 并查集 { int r = x ; while (r != set[r]) { r = set[r] ; } return r ; } int inse(char * str , Tnode * root) { Tnode *p = root ; while (*str) { int id = *str - 'a' ; if(p -> next[id] == NULL) { p -> next[id] = new Tnode ; } ++ str ; p = p -> next[id] ; } if(p -> du == 0) { p -> xu = ++ cnt ; // 顶点颜色的编号从 1 开始 } p -> du ++ ; d[p -> xu] = p -> du ; return p -> xu ; } int main() { memset(d , 0 , sizeof(d)) ; int i ; for(i = 1 ; i <= MAXN ; i ++) { set[i] = i ; } cnt = 0 ; Tnode *root = new Tnode ; while (scanf("%s%s" , s1 , s2) != EOF) { int x = inse(s1 , root) ; int y = inse(s2 , root) ; int tx = find(x) ; int ty = find(y) ; if(tx < ty) { set[ty] = tx ; } else { set[tx] = ty ; } } int fz = 0 ; // 判断图的连通的分支个数 int sumj = 0 ; // 统计奇度顶点的个数 for(i = 1 ; i <= cnt ; i ++) { if(set[i] == i) { fz ++ ; } if(d[i] % 2 == 1) { sumj ++ ; } } if(cnt == 0) { puts("Possible") ; } else if(fz == 1) { if(sumj > 2) { puts("Impossible") ; } else { puts("Possible") ; } } else { puts("Impossible") ; } return 0 ; }