巢穴

about:blank

P2513

trie+并查集+欧拉回路
有空数据..其实没影响..但是讨论里有个人说空数据输出Impossible...其实应该Possible...
这个人太邪恶了..
另外用数组写tire,re了不下5次..
最后改成了动态的..
1000+ms..还是挺慢的..

#include <iostream>
#include <stdio.h>
#include <string>
using namespace std;
struct node
{
 node *s[26];
 int count;
 int pos;
 node()
 {
  count=0;
  pos=0;
  for(int i=0;i<26;i++)
   s[i]=NULL;
 }
 
}*root;
int f[500010],o[500010];
int len=0,l=0;
char st1[11];
char st2[11];
int insert(char *ch)
{
     int ts=0;
     node *p=root;
     for (int i=0;i<strlen(ch);i++)
     {
         if ((p->s[ch[i]-'a'])==NULL)
         {
          p->s[ch[i]-'a']=new node();
         }
         p=p->s[ch[i]-'a'];
     }
     if (p->count==0)
     {
      len++;
      p->count=1;
      p->pos=len;
      ts=len;
      return ts;
     }
     else
     {
      ts=p->pos;
      return ts;
     }
     
     
}
int getfather(int x)
{
 if (f[x]==x) return x;
 f[x]=getfather(f[x]);
 return f[x];
}
int main()
{
    
    for (int i=0;i<500010;i++)
     {f[i]=i;o[i]=0;}
    root=new node();
    int u=0;
    while(scanf ("%s %s", st1, st2) != EOF)
    {
     u++;
     int x=insert(st1);
     int y=insert(st2);
     int fx=getfather(x);
     int fy=getfather(y);
     o[x]++;
     o[y]++;
     if (fx!=fy) f[fy]=fx;
    // if (u==5) break;
    }
    
    int itn=0;
    for (int i=1;i<=len;i++)
     if (getfather(i)==i) itn++;
    int odd=0;
    for (int i=1;i<=len;i++)
     if (o[i]%2) odd++;
    
    if (len==0)
    {
     cout<<"Possible"<<endl;
     exit(0);
    }
    if (itn==1&&(odd==2||odd==0)) 
    {
     cout<<"Possible"<<endl;
    }
    else
    {
     cout<<"Impossible"<<endl;
    }
   // system("pause");
     
    return 0;
}

posted on 2009-11-03 16:59 Vincent 阅读(81) 评论(0)  编辑 收藏 引用 所属分类: 数据结构与算法


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理