题意：有一些棒子，每一根的两头都有两个颜色，将这些棒子相连并且被两根棒子接头处是相同的颜色，求一些这样的棒子是否都可以全部连起来；
思路：首先用tree树给每一种颜色编号，然后用并查集+欧拉路（只有两个或零个奇数结点）；
代码：
View Code #include#include #include #include using namespace std; int f[500010] = { 0}; int n = 0; int nn[500010] ={ 0}; struct node { int num; node *next[27]; }; node *head = NULL; node *temp = NULL; node * get() { temp = new node; for(int i = 0;i < 27; ++i) temp->next[i] = NULL; temp->num = 0; return temp; } void init() { head = get(); for(int i = 0;i < 500010; ++i) { f[i] = i; nn[i] = 0; } n = 0; } char a[15] = { 0}; char b[15] ={ 0}; int x = 0; int y = 0; int qq(char *s) { node *temp1 = head; int q = 0; for(int i = 0; s[i]; ++i) { q = s[i] - 'a'; if(temp1->next[q] == NULL) temp1->next[q] = get(); temp1 = temp1->next[q]; } if(temp1->num != 0) return temp1->num; else { ++n; temp1->num = n; return n; } } int find(int x) { if(x != f[x]) f[x] = find(f[x]); return f[x]; } void unio(int a,int b) { int x = find(a); int y = find(b); if(x != y) f[x] = y; } bool check() { int num = 0; int tt = find(1); for(int i = 1;i <= n; ++i) { if(find(i) != tt) return 0; if(nn[i]%2) ++num; } if(num == 0 || num == 2) return 1; return 0; } int main() { //freopen("input.txt","r",stdin); init(); while(scanf("%s%s",a,b) != EOF) { x = qq(a); ++nn[x]; y = qq(b); ++nn[y]; unio(x,y); } if(check()) printf("Possible\n"); else printf("Impossible\n"); return 0; }