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.
早起一水
囧呆了
給很多木棍，兩端有顏色，問能不能是這些木棍首尾相接，并且保證相連接處顏色相同
一筆畫問題，判斷歐拉路
統(tǒng)計(jì)節(jié)點(diǎn)的度數(shù)，奇點(diǎn)個(gè)數(shù)為0或2，存在歐拉路
但這里是單詞作為點(diǎn)，所以要判斷
怎么判斷呢，好多方法，hash，trie，map（目前還不會(huì)）
這里我顯然用了trie這段時(shí)間學(xué)了這個(gè)，練下
判歐拉圖，還是是連通的才可以，所以得判連通，用并查集即可
或者麻煩的建圖，dfs一遍
father數(shù)組忘記初始化了，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++;//奇點(diǎn)個(gè)數(shù)
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;
}