poj 2513 連接火柴 字典樹+歐拉通路 好題

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

PossibleHint

Huge input,scanf is recommended.
Source

The UofA Local 2000.10.14
 
題意： 有很多個火彩 每頭都有顏色   相同的顏色可以和另外的火柴相接  問這些火柴能不能連接成一條線 
 
思路：  很明顯這是一個歐拉通路問題      一筆畫畫完整個通路 
用字典樹標記字符串對應的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;
}