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

本文主要是介绍POJ 2513 Colored Sticks(字典树+欧拉路径)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=11158

Colored Sticks

Time Limit: 5000MS

Memory Limit: 128000KB

64bit IO Format: %I64d & %I64u

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,int>写的，但是string是cin输入啊，而hint的提示要用scanf。这可怎么办？后来发现了神奇的字典树，轻便高效值得拥有！映射的问题解决了，然后就是欧拉路径/回路的判断了。
相关知识点：
欧拉回路和欧拉路径的判断
欧拉回路：
无向图：每个顶点的度数都是偶数，则存在欧拉回路。
有向图：每个顶点的入度都等于出度，则存在欧拉回路。
欧拉路径：
无向图：当且仅当该图所有顶点的度数为偶数或者除了两个度数为奇数外其余的全是偶数。
有向图：当且仅当该图所有顶点出度=入度或者一个顶点出度=入度+1，另一个顶点入度=出度+1，其他顶点出度=入度。
本题和hdu 1116（上一篇博客）稍有不同，这是无向图，那个是有向图（单词不可能倒着写）。判定条件不要混淆。相关博客： http://blog.csdn.net/zzran/article/details/9106329

#include <iostream>
#include <cstdio>
#include <cstring>
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 stringp->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 lengthreturn  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 countc[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;
}

这篇关于POJ 2513 Colored Sticks(字典树+欧拉路径)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！