Colored Sticks
| Time Limit: 5000MS |
|
Memory Limit: 128000K |
| Total Submissions: 24238 |
|
Accepted: 6381 |
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.
早起一水
囧呆了
给很多木棍，两端有颜色，问能不能是这些木棍首尾相接，并且保证相连接处颜色相同
一笔画问题，判断欧拉路
统计节点的度数，奇点个数为0或2，存在欧拉路
但这里是单词作为点，所以要判断
怎么判断呢，好多方法，hash，trie，map（目前还不会）
这里我显然用了trie这段时间学了这个，练下
判欧拉图，还是是连通的才可以，所以得判连通，用并查集即可
或者麻烦的建图，dfs一遍
father数组忘记初始化了，wa一次
改后忘记注视freopen了，wa一次
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cassert>
#include <iostream>
#include <sstream>
#include <fstream>
#include <map>
#include <set>
#include <vector>
#include <queue>
#include <algorithm>
#include <iomanip>
using namespace std;
int cnt;
struct node
{
int next[26];
int count;
int key;
void init()
{
memset(next,-1,sizeof(next));
count=0;
}
} s[6000005];
int father[250005],count1[250005],sind;
void cas_init()
{
s[0].init();
sind=1;
}
int ins(char str[])
{
int len=strlen(str);
int i,j,ind;
ind=0;
for(i=0; i<len; i++)
{
j=str[i]-'a';
if(s[ind].next[j]==-1)
{
s[sind].init();
s[ind].next[j]=sind++;
}
ind=s[ind].next[j];
}
if(s[ind].count==0)
{
s[ind].key=cnt++;
}
s[ind].count++;
return s[ind].key;
}
int find(int x)
{
if(x==father[x]) return x;
else
{
father[x]=find(father[x]);
return father[x];
}
}
void un(int a,int b)
{
father[find(a)]=find(father[b]);
}
int main()
{
int ca,cb;
char str1[21],str2[21];
cas_init();
cnt=0;
memset(count1,0,sizeof(count1));
for(int i=0; i<250005; i++) father[i]=i;
//freopen("in1.txt","r+",stdin);
while(scanf("%s%s",str1,str2)!=EOF)
{
//puts(str1);puts(str2);
ca=ins(str1);
cb=ins(str2);
//cout<<ca<<" "<<cb<<endl;
count1[ca]++;
count1[cb]++;
un(ca,cb);
}
if(cnt==0)
{
printf("Possible\n");
}
else
{
int tmp;
tmp=0;
for(int i=0; i<cnt; i++)
if(count1[i]%2==1)
tmp++;//奇点个数
ca=find(0);
for(int i=1; i<cnt; i++)
if(ca!=find(i))
{
tmp=-1;
break;
}
//printf("%d\n",cnt);
if(tmp==0||tmp==2)
printf("Possible\n");
else printf("Impossible\n");
}
//fclose(stdin);
return 0;
}