代码还比较易懂,直接贴了
#include<iostream>
#include<cstring>
using namespace std;
struct dictree
{
struct dictree * child[52];
int num;
}*root;
int n;
int ID;
int father[200010];
int rank[200010];
void create(int k);
int find(int k);
int Union(int a,int b);
int update(char *str);
void Delete(struct dictree * now);
int main()
{
int t;
char str1[25],str2[25];
int t1,t2;
while(cin>>t)
{
while(t--)
{
ID=0;
cin>>n;
create(n);
root=new struct dictree;
root->num=-1;
for(int i=0;i<52;i++)
root->child[i]=NULL;
for(i=0;i<n;i++)
{
scanf("%s%s",&str1,&str2);
t1=update(str1);
t2=update(str2);
t1=find(t1);
t2=find(t2);
printf("%d\n",Union(t1,t2));
}
}
}
return 0;
}
int update(char *str)
{
struct dictree * now,*newnode;
int c;
now=root;
for(int i=0;i<strlen(str);i++)
{
if(str[i]>='a' && str[i]<='z')
c=str[i]-'a';
else
c=str[i]-'A'+26;
if(now->child[c]!=NULL)
{
now=now->child[c];
}
else
{
newnode=new struct dictree;
newnode->num=-1;
for(int i=0;i<52;i++)
{
newnode->child[i]=NULL;
}
now->child[c]=newnode;
now=newnode;
}
}
if(now->num==-1)
now->num=ID++;
return now->num;
}
void create(int k)
{
for(int i=0;i<2*k;i++)
{
father[i]=i;
rank[i]=1;
}
}
int find(int k)
{
if(father[k]!=k)
{
father[k]=find(father[k]);
}
else
return k;
return father[k];
}
int Union(int a,int b)
{
if(a==b)
return rank[a];
if(rank[a]>rank[b])
{
father[b]=a;
rank[a]+=rank[b];
rank[b]=0;
return rank[a];
}
else
{
father[a]=b;
rank[b]+=rank[a];
rank[a]=0;
return rank[b];
}
}
分享到:
相关推荐
杭电ACM课件2014版之 (HDUACM201403版_06)并查集(最小生成树)
hdu 1695 GCD(欧拉函数+容斥原理).docx
(HDUACM2010版_06)并查集(最小生成树(HDUACM2010版_06)并查集(最小生成树(HDUACM2010版_06)并查集(最小生成树(HDUACM2010版_06)并查集(最小生成树
acm hdu as easy as a+b
ACM题库,一些题目和答案,以及解题报告,传上来共享
【HDU 3993】田忌赛马 题解+勘误 题解这里就略写一下了,主要是勘误。 这道题是2011年之前的多校训练题,2020年的今天,我们一个集训队全部挂在上面了。最后在HDU看到了9年前的讨论区,才知道这题有如下问题: speed...
hdu 1166线段树代码
杭电OnlineJudge 200-2099的解题报告
从简单入门到偏中等的几个题,线段树很灵活,主要懂了lazy操作,其他的自己yy吧。
hdu 3341(ac自动机+状态压缩) 题意:容易理解... 思路:首先一开始容易想到要用到dp,开设一个dp[41][41][41][41][501]的数组来解决,但是明显内存已经超出范围了,于是就想如何减少内存呢?只要知道A、T、C、G其中...
本人准备2020年保研机试时刷的题目(虽然最后机试取消了,...来自某中流985,在HDU和vjudge平台上大概刷了400道。本文件地图(excel表格)包含了绝大部分我刷过的题目,笔记中具有思路、代码、总结和心得。 大佬勿入!
hdu 1166线段树
acm 技术大牛 课件 HDU 自学必备课件 全套齐全 (lecture_01)初识ACM (lecture_02)简单数学题 (lecture_03)递推求解 (lecture_04)动态规划(1)_ (lecture_05)计算几何基础_ (lecture_06)母函数 ...并查集
300+ AC 代码 。 大数 , 线段树 , 字符串 , dp.....
使用并查集+贪心:先将已有边的权值从大到小排序,又n个点只需n-1条边,这时再遍历一遍,将有边的两点合并为一个队伍,当边的数量达到n-1时退出循环,因为此时已达到最小生成树。 边的权值由大到小排序是因为要将大...
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
friends. Uh... very very good friends -________-b FF is a bad boy, he is always wooing TT to play the following game with him. This is a very humdrum game. To begin with, TT should write down a ...