POJ 2513 Colored Sticks(字典树+欧拉路径)

POJ 2513 Colored Sticks(字典树+欧拉路径)

题目：​​Sticks​​

​​Submit​​​ ​​Status​​

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.

开始想用map写的，但是string是cin输入啊，而hint的提示要用scanf。这可怎么办？后来发现了神奇的字典树，轻便高效值得拥有！映射的问题解决了，然后就是欧拉路径/回路的判断了。

相关知识点：

欧拉回路和欧拉路径的判断

欧拉回路：

无向图：每个顶点的度数都是偶数，则存在欧拉回路。

有向图：每个顶点的入度都等于出度，则存在欧拉回路。

欧拉路径：

无向图：当且仅当该图所有顶点的度数为偶数 或者 除了两个度数为奇数外其余的全是偶数。

有向图：当且仅当该图所有顶点 出度=入度 或者 一个顶点 出度=入度+1，另一个顶点 入度=出度+1，其他顶点 出度=入度。

本题和hdu 1116（上一篇博客）稍有不同，这是无向图，那个是有向图（单词不可能倒着写）。判定条件不要混淆。

#include #include #include using namespace std;const int maxn=5e5+5;struct node{ int num; bool is_word; node *next[26]; node(){ num=is_word=0; memset(next,NULL,sizeof(next)); }};node *root;int n,c[maxn],f[maxn];void insert(char s[]){ node *p=root; for(int i=0;s[i];i++){ int dex=s[i]-'a'; if(p->next[dex]==0) p->next[dex]=new node(); p=p->next[dex]; } if(p->is_word==0){ // important! because of num++ p->num=++n; //num is dex of string p->is_word=1; }}int find(int x){ if(x==f[x]) return x; f[x]=find(f[x]); return f[x];}int getdex(char s[]){ node *p=root; for(int i=0;s[i];p=p->next[s[i]-'a'],i++); // not need length return p->num;}int main(){ //freopen("cin.txt","r",stdin); n=0; memset(c,0,sizeof(c)); memset(f,0,sizeof(f)); root=new node(); char a[15],b[15]; int adex,bdex; while(~scanf("%s%s",a,b)){ insert(a); insert(b); adex=getdex(a); bdex=getdex(b); c[adex]++; //all count c[bdex]++; if(!f[adex]) f[adex]=adex; // U gather。 if(!f[bdex]) f[bdex]=bdex; f[find(adex)]=f[find(bdex)]; } int oddsum=0; bool judge=1; for(int i=1;i<=n;i++){ if(c[i]&1) oddsum++; if(find(i)!=f[1]){ judge=0; break; } } if((oddsum==0 || oddsum==2)&&judge) puts("Possible"); else puts("Impossible"); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。