poj 2513 连接火柴 字典树+欧拉通路 好题

时间:2021-10-18 05:18:07
Colored Sticks
Time Limit: 5000MS   Memory Limit: 128000K
Total Submissions: 27134   Accepted: 7186

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.

Source

 
题意: 有很多个火彩 每头都有颜色   相同的颜色可以和另外的火柴相接  问这些火柴能不能连接成一条线 
 
思路:  很明显这是一个欧拉通路问题      一笔画画完整个通路 
用字典树标记字符串对应的id
用map超时
#include<stdio.h>
#include<string>
#include<string.h>
#include<map>
#include<malloc.h>
using namespace std;
#define N 250000+10
char s1[100],s2[100];
int rank[N],fa[N],num[N],co=0;
struct haha
{
int id;
struct haha *next[26];
}*root;
struct haha * creat()
{
int i;
struct haha *p;
p=(struct haha *)malloc(sizeof(struct haha));
p->id=-1;
for(i=0;i<26;i++) p->next[i]=NULL;
return p;
};
int update(char *s)
{
int d,pos,i;
struct haha *p;
p=root;d=strlen(s);
for(i=0;i<d;i++)
{
pos=s[i]-'a';
if(p->next[pos]==NULL)
{
p->next[pos]=creat();
p=p->next[pos];
}
else
{
p=p->next[pos];
}
}
if(p->id==-1)
p->id=co++;
return p->id;
}
int find(int n)
{
return n==fa[n]?n:fa[n]=find(fa[n]);
}
void join(int a,int b)
{
if(rank[a]>rank[b])
{
fa[b]=a;
rank[a]+=rank[b];
}
else
{
fa[a]=b;
rank[b]+=rank[a];
}
}
int main()
{
int i,j,k,cnt=0,a,b,rem;
for(i=0;i<N;i++)
{
rank[i]=1;fa[i]=i;
}
memset(num,0,sizeof(num));
root=creat();
while(scanf("%s %s",s1,s2)!=EOF)
{
a=update(s1);
b=update(s2); num[a]++;num[b]++;
a=find(a);b=find(b);
if(a==b) continue;
join(a,b);
}
cnt=0;
int temp=find(0);
for(i=0;i<N;i++)
{
if(num[i]%2==1) cnt++;
if(cnt>2) {printf("Impossible\n");return 0;}
if(num[i]!=0&&find(i)!=temp) {printf("Impossible\n");return 0;}
}
printf("Possible\n");
return 0;
}