Colored Sticks
| Time Limit: 5000MS | Memory Limit: 128000K | |
| Total Submissions: 35612 | Accepted: 9324 |
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
【分析】欧拉通路的判定。一开始用map给字符串编号，超时了，后来在网上烤来一份字典树hash.
#include <iostream> #include <cstdio> #include <cstdlib> #include <cmath> #include <algorithm> #include <climits> #include <cstring> #include <string> #include <set> #include <map> #include <queue> #include <stack> #include <vector> #include <list> #include<functional> #define mod 1000000007 #define inf 0x3f3f3f3f #define pi acos(-1.0) using namespace std; typedef long long ll; const int N=5000005; const int M=1005; ll power(ll a,int b,ll c){ll ans=1;while(b){if(b%2==1){ans=(ans*a)%c;b--;}b/=2;a=a*a%c;}return ans;} int parent[N]; const int MAX=26; int degree[N];//度数 int color;//颜色编号，从0开始，最后就是颜色总数 int Find(int x) { if(parent[x] != x) parent[x] = Find(parent[x]); return parent[x]; }//查找并返回节点x所属集合的根节点 void Union(int x,int y) { x = Find(x); y = Find(y); if(x == y) return; parent[y] = x; }//将两个不同集合的元素进行合并 struct Trie { bool isWord; struct Trie *next[MAX]; int id; }; int insert(Trie *root,char *word)//返回颜色编号 { Trie *p=root; int i=0; while(word[i]!=' ') { if(p->next[word[i]-'a']==NULL) { Trie *temp=new Trie; temp->isWord=false; for(int j=0;j<MAX;j++) temp->next[j]=NULL; temp->isWord=false; temp->id=0; p->next[word[i]-'a']=temp; } p=p->next[word[i]-'a']; i++; } if(p->isWord) { return p->id; } else { p->isWord=true; p->id=color++; return p->id; } } void del(Trie *root) { for(int i=0;i<MAX;i++) { if(root->next[i]!=NULL) del(root->next[i]); } free(root); } int main() { char str1[20],str2[20]; Trie *root=new Trie; for(int i=0;i<MAX;i++) root->next[i]=NULL; root->isWord=false; root->id=0;//初始化 color=0; for(int i=0;i<N;i++)parent[i]=i; memset(degree,0,sizeof(degree)); while(scanf("%s%s",&str1,&str2)!=EOF) { int t1=insert(root,str1); int t2=insert(root,str2); // printf("%d %d ",t1,t2); degree[t1]++; degree[t2]++; Union(t1,t2); } int cnt1=0,cnt2=0; for(int i=0;i<color;i++) { if(parent[i]==i)cnt1++; if(degree[i]%2==1)cnt2++; if(cnt1>1)break; if(cnt2>2)break; } //数据比较坑人，存在0根木棒的情况，此时cnt1==0 if((cnt1==0||cnt1==1)&&(cnt2==0||cnt2==2)) printf("Possible "); else printf("Impossible "); //del(root);//单组输入可以不释放空间，可以节省时间 return 0; }