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 閱讀(885)
評論(1) 編輯 收藏 引用 所屬分類:
acm 、
數據結構