http://acm.pku.edu.cn/JudgeOnline/problem?id=2513这道题是直接拿前几天写得模版改的；做了几个修改
首先删掉了search，这道题的确不需要，本来没删，代码实在太长,逼得我没办法
第二个，把trie中num[]的意思改掉了，num[]现在存的是字符串在一个数组的标记，
相当于map的实现，通过这样我把一个字符串和一个标号对应上了，方便了并查集的操作
果然很久没碰并查集了，一写就出问题，
主要是我union_set是居然忘了要先find_set一下，这样写针对下面这组数据就会出现问题：
a b
b a
a a
还有一个就是这道题的空输入问题，要输出possible，而不是Impossible
一下是我的垃圾代码，跑了500多，有谁有更好的发我邮箱哈: zhangjia888334@sohu.com
#include<iostream>
#include<cstring>
#define keyNum 26
#define MaxN 500005
struct node{
int parent;
int rank;
int num;//这个颜色出现的次数
node()
{
num=rank=0;
parent=-1;
}
};
node colour[MaxN];
int id=0;//数组标记
struct trie{
struct trieNode{//trie结点的结构
trieNode *link[keyNum];//下标为 'a' , 'b' , 'c' , , 'z' 的指针数组
int num[keyNum];//插入这个单词在数组中的位置
trieNode(){
memset(num,-1,sizeof(num));//-1表示还未插入数组
memset(link,NULL,sizeof(link));
}
void init(){
memset(link,NULL,sizeof(link));
memset(num,-1,sizeof(num));
}
};
trieNode* root;
trie()
{
root=(trieNode*)malloc(sizeof(trieNode));//初始化时为root申请了空间
root->init();
}
int Insert(char []);//返回数组中的位置
void Delete(trieNode*);//释放空间
};
void trie::Delete(trieNode* t)
{
int i;
for(i=0;i<keyNum;i++)
if(t->link[i])Delete(t->link[i]);
memset(t->num,0,sizeof(t->num));
delete(t);
}
int trie::Insert(char x[])
{
trieNode *current=root;
int i=1;
while(x[i]){
if(current->link[x[i-1]-'a']==NULL){
current->link[x[i-1]-'a']=(trieNode*)malloc(sizeof(trieNode));
(current->link[x[i-1]-'a'])->init();
}
current=current->link[x[i-1]-'a'];
i++;
}
if(current->num[x[i-1]-'a']==-1)
current->num[x[i-1]-'a']=id++;
colour[current->num[x[i-1]-'a']].num++;//出现的次数++
return current->num[x[i-1]-'a'];
}
void init()
{
int i;
for(i=0;i<MaxN;i++)
colour[i].parent=i;
}
void union_set(int x,int y)
{
if(colour[x].rank>colour[y].rank)
colour[y].parent=x;
else {
colour[x].parent=y;
if(colour[x].rank==colour[y].rank)
colour[y].rank++;
}
}
int find_set(int x)
{
if(x!=colour[x].parent)
colour[x].parent=find_set(colour[x].parent);
return colour[x].parent;
}
bool comman_father()
{
int i,p=0;
p=find_set(0);
for(i=1;i<id;i++)
if(find_set(i)!=p)return false;
return true;
}
void solve()
{
if(comman_father()==false){
printf("Impossible\n");
return;
}
int i,head_end=0;
for(i=0;i<id;i++)
if(colour[i].num%2==1)//判断头和尾
head_end++;
if(head_end==2||!head_end)//一个没回路，一个是有回路
printf("Possible\n");
else printf("Impossible\n");
}
int main()
{
char colr1[12],colr2[12];
trie a;
int ncolr1,ncolr2;
init();
while(scanf("%s%s",colr1,colr2)!=EOF){
ncolr1=a.Insert(colr1);
ncolr2=a.Insert(colr2);
union_set(find_set(ncolr1),find_set(ncolr2));
}
//下面判断有几个parent，若有多个失败
solve();
a.Delete(a.root);
return 0
}
posted on 2008-04-08 18:35
zoyi 阅读(873)
评论(1) 编辑 收藏 引用 所属分类:
acm 、
数据结构