作者：六月的 | 来源：互联网 | 2023-06-29 17:57
#1066:无间道之并查集时间限制:20000ms单点时限:1000ms内存限制:256MB描述这天天气晴朗、阳光明媚、鸟语花香，空气中弥漫着春天的气息……额，说远了，总之，小Hi和小Ho决定趁着
#1066 : 无间道之并查集
时间限制:20000ms单点时限:1000ms内存限制:256MB
描述
这天天气晴朗、阳光明媚、鸟语花香，空气中弥漫着春天的气息……额，说远了，总之，小Hi和小Ho决定趁着这朗朗春光出去玩。
但是刚刚离开居住的宾馆不久，抄近道不小心走入了一条偏僻小道的小Hi和小Ho就发现自己的前方走来了几个彪形大汉，定睛一看还都是地地道道的黑人兄弟！小Hi和小Ho这下就慌了神，捡肥皂事小，这一身百把来斤别一不小心葬身他乡可就没处说去了。
就在两人正举足无措之时，为首的黑叔叔从怀里掏出了一件东西——两张花花绿绿的纸，分别递给了小Hi和小Ho。
小Hi和小Ho接过来，只见上面写道（译为中文）：“本地最大的帮派——青龙帮，诚邀您的加入！”下面还详细的列出了加入青龙帮的种种好处。
于是两人略感心安，在同黑叔叔们交谈一番之后，已是均感相见恨晚。同时，在小Hi和小Ho表示自己不日便将回国之后，黑叔叔们也没有再提加入帮派之事，但是那为首的黑叔叔思索一会，开口道（译为中文）：“我现在有一个难题，思索了很久也没法子解决，既然你们俩都是高材生，不如来帮我看看。”
小Hi和小Ho点了点头表示没问题，于是黑叔叔继续说道：“这个问题是这样的，我们帮派最近混进了许多警察的卧底，但是在我们的调查过程中只能够知道诸如‘某人和另一个人是同阵营的’这样的信息，虽然没有办法知道他们具体是哪个阵营的，但是这样的信息也是很重要的，因为我们经常会想要知道某两个人究竟是不是同一阵营的。”
小Hi和小Ho赞同的点了点头，毕竟无间道也都是他们看过的。
黑叔叔接着说道：“于是现在问题就来了，我希望你们能写出这样一个程序，我会有两种操作，一种是告诉它哪两个人是同一阵营的，而另一种是询问某两个人是不是同一阵营的……既然你们就要回国了，不如现在就去我们帮派的总部写好这个程序再走把。”
为了生命安全与……小Hi和小Ho都不得不解决这个问题！那么他们究竟从何下手呢？
提示：说起来其实就是不断的合并集合嘛~输入
每个测试点（输入文件）有且仅有一组测试数据。
每组测试数据的第1行为一个整数N，表示黑叔叔总共进行的操作次数。
每组测试数据的第2~N+1行，每行分别描述黑叔叔的一次操作，其中第i+1行为一个整数op_i和两个由大小写字母组成的字符串Name1_i, Name2_i，其中op_i只可能为0或1，当op_i=0时，表示黑叔叔判定Name1_i和Name2_i是同一阵营的，当op_i=1时，表示黑叔叔希望知道Name1_i和Name2_i是否为同一阵营的。
对于100%的数据，满足N<=10^5, 且数据中所有涉及的人物中不存在两个名字相同的人（即姓名唯一的确定了一个人），对于所有的i，满足Name1_i和Name2_i是不同的两个人。
输出
对于每组测试数据，对于黑叔叔每次op_i=1的操作，输出一行，表示查询的结果：如果根据已知信息（即这次操作之前的所有op_i=0的操作），可以判定询问中的两个人是同一阵营的，则输出yes，否则输出no。
-
样例输入
-
10
0 Steven David
0 Lcch Dzx
1 Lcch Dzx
1 David Dzx
0 Lcch David
0 Frank Dzx
1 Steven Dzx
1 Frank David
0 Steven Dzx
0 Dzx Frank
-
样例输出
-
yes
no
yes
yes
EmacsNormalVim
安装mysql累死了 卸载了安装 安装了卸载 安装过程中无聊 就做个水题~
Trie树查找People的序号 并查集判断两个人是否为集合
#include
struct Trie
{
int id;
//A+32='a';
Trie *word[65];
Trie()
{
for(int i=0;i<65;i++)
word[i]=NULL;
id=-1;
}
};
int ID;
int fa[100000+10];
//查找并更新Trie树
int findAndUpdate(char *str,Trie *trie)
{
for(*str;*str;str++)
{
//如果当前字符不存在 开辟空间
if(trie->word[*str-'A']==NULL)
{
trie->word[*str-'A']=new Trie();
}
trie=trie->word[*str-'A'];
}
//如果这个单词未出现过 ID++
if(trie->id==-1)
{
trie->id=ID++;
}
return trie->id;
}
//并查集初始化
void init(int n)
{
for(int i=0;i<=n;i++)
fa[i]=i;
}
//并查集查找根
int find(int x)
{
if(fa[x]!=x) fa[x]=find(fa[x]);
return fa[x];
}
//并查集的合并
void unionPeo(int x1,int x2)
{
int x=find(x1);
int y=find(x2);
if(x!=y)
{
fa[x]=y;
}
}
int main()
{
int n;
Trie *trie=new Trie();
ID=0;
scanf("%d",&n);
init(n);
while(n--)
{
int x;
char name1[200];
char name2[200];
scanf("%d %s %s",&x,name1,name2);
int x1=findAndUpdate(name1,trie);
int x2=findAndUpdate(name2,trie);
if(x==0)
{
unionPeo(x1,x2);
}
if(x==1)
{
if(find(x1)==find(x2))
{
puts("yes");
}
else
{
puts("no");
}
}
}
return 0;
}
京公网安备 11010802041100号