題意：有一些木棍，木棍的兩邊各有一種顏色，如果兩根木棍的一邊顏色相同的話，那麼就可以連在一起，問能不能完全連成一根
思路：不在是簡單的歐拉路，如果能將顏色表達成一個數字的話就能轉化為歐拉路了，
用Trie樹來優化，再用並查集判斷是否為歐拉路，將pre[]初始化為-1，加快速度
#include #include #include #include #include using namespace std; const int N = 15; const int M = 1000010; struct Trie{ int num; Trie *next[26]; }*Head; Trie trie[M]; char u[N],v[N]; int num,n,top,total,flag; int pre[M],in[M]; int Find_set(int x){ return pre[x] == -1 ? x : (pre[x] = Find_set(pre[x])); } void Make_Set(int x,int y){ int root1 = Find_set(x); int root2 = Find_set(y); if (root1 != root2) pre[root2] = root1; } int insert(char *str){ Head = &trie[0]; int len = strlen(str); for (int i = 0; i < len; i++){ int temp = str[i] - 'a'; if (Head->next[temp] == NULL) Head->next[temp] = &trie[++num]; Head = Head->next[temp]; } if (Head->num == 0) Head->num = top++; return Head->num; } void init(){ num = total = 0,top = 1,flag = 1; memset(in,0,sizeof(in)); memset(pre,-1,sizeof(pre)); for (int i = 0; i < 20; i++){ trie[i].num = 0; for (int j = 0; j < 26; j++) trie[i].next[j] = NULL; } } int main(){ int tmp,temp; init(); while (scanf("%s %s",u,v) != EOF){ tmp = insert(u),temp = insert(v); in[tmp]++,in[temp]++; Make_Set(tmp,temp); } int root = Find_set(1); for (int i = 1; i < top; i++){ if (root != Find_set(i)){ flag = 0; break; } if (in[i] & 1) total++; if (total > 2) break; } if ((total == 0 || total == 2) && flag == 1) printf("Possible\n"); else printf("Impossible\n"); return 0; }
MFC單文檔帶窗體創建，mfc文檔窗體 我用的vs
[NOIP2014]解方程，noip2014解方程3732
C++學習筆記7——模板，學習筆記7模板函數模板： #in
DX筆記之一---Direct3D基礎，dx筆記---dir
二叉樹的深度，二叉樹深度題目：輸入一棵二叉樹的根節點，求該樹
Accelerated C++ 學習筆記及題解----第二章
