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

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

阅读量：6242 次

发布时间：2019-06-22

本文共 1933 字，大约阅读时间需要 6 分钟。

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 redred violetcyan blueblue magentamagenta cyan

Sample Output

Possible

Hint

Huge input,scanf is recommended.

Source

题意：有很多个火彩每头都有颜色相同的颜色可以和另外的火柴相接问这些火柴能不能连接成一条线

思路：很明显这是一个欧拉通路问题一笔画画完整个通路

用字典树标记字符串对应的id

用map超时

#include
     
      #include
      
       #include
       
        #include
        #include
         
          using namespace std;#define N 250000+10char 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
          
           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
           
            2) {printf("Impossible\n");return 0;} if(num[i]!=0&&find(i)!=temp) {printf("Impossible\n");return 0;} } printf("Possible\n"); return 0;}

转载地址：http://issia.baihongyu.com/

你可能感兴趣的文章