首页 > 代码库 > POJ2513 Colored Sticks (并查集+trie)

POJ2513 Colored Sticks (并查集+trie)

2024-07-22 13:13:18   213人阅读

传送门
Colored Sticks
Time Limit: 5000MS Memory Limit: 128000K
   

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 redred violetcyan blueblue magentamagenta cyan

Sample Output

Possible

Hint

Huge input,scanf is recommended.

Source

The UofA Local 2000.10.14
 
回顾了一下欧拉图的知识。。整个图的奇度点个数如果>=3或只有1个 就不能一笔画画完
中间re了几次。。因为trie里我开了n*30，但是外面数组只开了n...
 1 #include<set> 2 #include<queue> 3 #include<cstdio> 4 #include<cstdlib> 5 #include<cstring> 6 #include<iostream> 7 #include<algorithm> 8 using namespace std; 9 const int N = 250010;10 #define For(i,n) for(int i=1;i<=n;i++)11 #define For0(i,n) for(int i=0;i<n;i++)12 #define Rep(i,l,r) for(int i=l;i<=r;i++)13 14 char s1[11],s2[11];15 int n,in[N*30],fa[N*30],ans;16 struct Trie{17     int sz,ch[N*30][26],v[N*30],Loc[N*30];18     Trie(){sz=1;}19     int insert(char st[]){20         int now=1;v[1]++;int len=strlen(st);21         For0(i,len){22             int id=st[i]-‘a‘;23             if(!ch[now][id]) ch[now][id]=++sz;24             v[now=ch[now][id]]++;25         }26         if(Loc[now]) return Loc[now];27         else         return Loc[now]=++n;28     }29 }trie;30 31 int find(int i){32     if(fa[i]==i) return i;33     else         return fa[i]=find(fa[i]);34 }35 36 int main(){37     #ifndef ONLINE_JUDGE38         freopen("trie.in","r",stdin);39     #endif // ONLINE_JUDGE40     For0(i,N*30) fa[i]=i;41     while(scanf("%s %s",&s1,&s2)!=EOF){42         int x=trie.insert(s1),y=trie.insert(s2);43         in[x]++;in[y]++;44         int fx=find(x),fy=find(y);45         if(fx!=fy) fa[fx]=fy;46     }47     int checks=find(1);48     Rep(i,2,n) if(find(i)!=checks){49         puts("Impossible\n");50         return 0;51     }52     For(i,n) {53         in[i]=in[i]%2;54         if(in[i]) ans++;55     }56     if(ans==1||ans>=3) puts("Impossible");57     else               puts("Possible");58     return 0;59 }

 

POJ2513 Colored Sticks (并查集+trie)


联系
我们