题意是 如果2个人是朋友 则他们朋友的朋友也是他们的朋友 这样就组成了一圈朋友 他们就有很多朋友了 输入 2个人的名字 为2个字符串
表示2个人是朋友 并且在同时输出他们的朋友圈有多大 注意 人数最多为100000 很多哦
显然不能用 暴力去给字符串分配编号 太大了人 那样肯定超时
就必须要用字典树了
#include<stdio.h>
#include<malloc.h>
#include<string.h>
#include<stdlib.h>
struct haha
{
struct haha *next[52];
int cnt;
};
struct haha *root;
struct haha *build()
{
struct haha *p;
int i;
p=(struct haha *)malloc(sizeof(struct haha));
for(i=0;i<52;i++)
p->next[i]=NULL;
p->cnt=0;
return p;
}
int cs,parent[200010],rank[200010];
int getnum(char *t)
{
int d,i,u;
struct haha *p;
p=root;
d=strlen(t);
for(i=0;i<d;i++)
{
if(t[i]>='a'&&t[i]<='z')
u=t[i]-'a';
else u=t[i]-'A'+26;//前面的26个位置是给小写字母留着的 不能占用 所以加26
if(p->next[u]==NULL)
{
p->next[u]=build();
p=p->next[u];
}
else p=p->next[u];
}
if(p->cnt==0) p->cnt=++cs;//走到串对应的终点了 这时候在串的末尾对应的节点上给其编号
return p->cnt; //分配的编号
}
int find(int x)
{
return x==parent[x]?x:(parent[x]=find(parent[x]));
}
void del(struct haha *p) {
int i;
for ( i=0; i<52; ++i)
{
if (p->next[i]) del(p->next[i]);
}
free(p);
p = NULL;
}
int main()
{
int cas,i,n,n1,n2;
char s1[25],s2[25];
while(scanf("%d",&cas)!=EOF)
{
while(cas--)
{
cs=0;
scanf("%d",&n);
for(i=0;i<=n+5;i++)
{
parent[i]=i;
rank[i]=1;
}
root=build();
for(i=1;i<=n;i++)
{
scanf("%s %s",s1,s2);
n1=getnum(s1);
n2=getnum(s2);
// printf("n1=%d n2=%d ",n1,n2);
n1=find(n1);
n2=find(n2);
if(n1!=n2) //
{
parent[n2]=n1;
rank[n1]+=rank[n2];//rank内的内容为当前集合的元素个数
}
printf("%d\n",rank[n1]);
}
del(root);//删除整棵树 每次都要删除整棵树 否则会错
}
}
return 0;
}
分享到:
相关推荐
杭电ACM课件2014版之 (HDUACM201403版_06)并查集(最小生成树)
(HDUACM2010版_06)并查集(最小生成树(HDUACM2010版_06)并查集(最小生成树(HDUACM2010版_06)并查集(最小生成树(HDUACM2010版_06)并查集(最小生成树
hdu 1166线段树代码
hdu 1166线段树
图论〔Graph Theory〕是数学的一个分支。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形,这种图形通常用来描述某些事物之间的某种特定关系,用点代表事物,用连接两点的线表示相应两个...
acm 技术大牛 课件 HDU 自学必备课件 全套齐全 (lecture_01)初识ACM (lecture_02)简单数学题 (lecture_03)递推求解 (lecture_04)动态规划(1)_ (lecture_05)计算几何基础_ (lecture_06)母函数 ...并查集
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
hdu1001解题报告
HDU1059的代码
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu2101AC代码
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
搜索 dfs 解题代码 hdu1241
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
使用并查集+贪心:先将已有边的权值从大到小排序,又n个点只需n-1条边,这时再遍历一遍,将有边的两点合并为一个队伍,当边的数量达到n-1时退出循环,因为此时已达到最小生成树。 边的权值由大到小排序是因为要将大...