題目鏈接：點擊打開鏈接

Colored Sticks

Time Limit: 5000MS	?	Memory Limit: 128000K
Total Submissions: 39392	?	Accepted: 10271

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

Hint

Huge input,scanf is recommended.

題目大意：給出n根木棒，木棒兩段顏色，只有顏色相同才可以連接，問是否能連成一根木棒。

思路：顏色轉(zhuǎn)化成數(shù)字。兩個方法：①map（超時）②字典樹。 連成一根木棒，并查集+歐拉回路

AC代碼：

#include<iostream> #include<algorithm> #include<cstdio> #include<cstdlib> #include<cstring> using namespace std; const int MAXN = 500010; int father[MAXN]; const int MAX = 26; int degree[MAXN];//度數(shù) int color; //并查集************************ int find(int x) { if(father[x] == -1)return x;return father[x] = find(father[x]); }void Union(int x, int y) {int fx = find(x);int fy = find(y);if(fx != fy)father[fx] = fy; } //字典樹**************************** typedef struct Trie_Node{ bool isword;//是否是單詞結(jié)束 int id;//編號 struct Trie_Node *next[MAX];Trie_Node() {//初始化 isword = false;int id = 0;for(int i = 0; i < MAX; i++)next[i] = NULL;} }trie;int insert(trie *root, char *s) {trie *p = root;int i = 0;while(s[i]) {//跑s串 if(p->next[s[i]-'a'] == NULL) {//如果該位置 找不到 s[i]， 就開一個，指向它 trie *temp = new trie();p->next[s[i]-'a'] = temp;} p = p->next[s[i]-'a'];//繼續(xù)跑 i++;}if(p->isword)//如果之前有過了，直接返回編號 return p->id;else {//之前沒有，就先標(biāo)記，然后賦值，返回值。 p->isword = true;p->id = color++;return p->id;} }void del(trie *root) {//刪除 for(int i = 0; i < 26; i++) {if(root->next[i] != NULL)//這個節(jié)點還有26個 del(root->next[i]);}free(root); } int main() {char s1[20], s2[20];trie *root = new trie();color = 0;memset(father, -1, sizeof(father));//初始-1 并查集都可以這樣寫，這道題的顏色編號每處理，這樣寫更好 memset(degree, 0, sizeof(degree));while(~scanf("%s%s", s1, s2)) {int t1 = insert(root, s1);//插入字典樹，返回編號 int t2 = insert(root, s2);degree[t1]++;//入讀++ degree[t2]++;Union(t1, t2);}bool flag = true;int tt = find(0);//找到根，每個的祖先都應(yīng)該是它 int cnt = 0;for(int i = 0; i < color; i++) {if(find(i) != tt) flag = false;if(!flag) break;if(degree[i]%2 == 1) cnt++;// 度數(shù)為奇數(shù)只能是0 或者 2 if(cnt > 2) flag = false;}if(cnt == 1) flag =false;if(flag) printf("Possible\n");else printf("Impossible\n");del(root); }

?推薦博客：神犇kuangbin ? ? ? ?淺談字典樹

轉(zhuǎn)載于:https://www.cnblogs.com/ACMerszl/p/9572963.html

總結(jié)

以上是生活随笔為你收集整理的POJ2513-Colored Sticks的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。