关键词：
C - Junk-Mail Filter HDU - 2473
题目大意：就是一堆信件，然后有两个操作，一个是把一堆信件归在一个文件夹，一个就是把一个信件从文件夹中取出，最后问有多少个文件夹，一开始所有信件都是单独的文件夹。
其实就是一个简单的并查集删除的操作，当删除时就创建新的结点来代替它,要注意的是数组的范围，虽然信件只有10的5次方，但是操作有10的6次方，因为删除时还得创建新节点，所以数组一定要开大，不然不是WR就是TL。最后的输出可以直接用set，也可以用数组标记信件是归在哪个文件夹，注意的是后面创建的结点是虚拟的，真实的信件有对它们的映射，所以最后统计时只考虑真实信件。
1 #include<cstdio> 2 #include<iostream> 3 #include<set> 4 using namespace std; 5 struct Email 6 int id,gen; 7 em[1201108];//要够大 8 int n,m; 9 int gui(int x); 10 void bing(int x,int y); 11 void del(int x); 12 int main() 13 14 int i,x,y,test=0; 15 char c; 16 while(scanf("%d%d",&n,&m)!=EOF&&(n||m)) 17 18 int N=n; 19 set<int> s; 20 for(i=0;i<n;i++) 21 22 em[i].id=i; 23 em[i].gen=i; 24 //初始自己映射自己，自己是自己的根节点。。。。 25 while(m--) 26 27 cin>>c; 28 if(c==‘M‘) 29 30 scanf("%d%d",&x,&y); 31 bing(em[x].id,em[y].id); 32 33 else 34 35 scanf("%d",&x); 36 del(x); 37 38 39 for(i=0;i<N;i++)//只考虑真实信件 40 s.insert(gui(em[i].id));//每个集合的根节点只记录一次 41 printf("Case #%d: %d ",++test,s.size()); 42 43 return 0; 44 45 int gui(int x) 46 47 if(em[x].gen==x) 48 return x; 49 return em[x].gen=gui(em[x].gen); 50 51 void bing(int x,int y)//对节点所映射的节点进行并操作 52 53 int bx=gui(x); 54 int by=gui(y); 55 if(bx!=by) 56 em[by].gen=bx; 57 return ; 58 59 void del(int x)//创造虚拟节点来代替原来节点 60 61 em[x].id=n;//节点映射到新创建的虚拟节点 62 em[n].gen=n; 63 n++; 64 return ; 65
并查集的基本操作和用法(代码片段)
并查集并查集的作用：1.合并区间2.判断两个数是否再同一个集合之中3.寻找联通子图的的个数并查集的关键函数find(x)与p[]数组寻找x的祖宗节点/* find函数用于寻找祖宗节点*/intfind(intx)if(p[x]!=x) find(p[x])returnp[x];/* p[N] 存储每... 查看详情
nowcoder106c.professionalmanager(统计并查集的个数)(代码片段)
题意：给出四种操作：1.合并u，v两棵树2.从u所在的集合中删除u3.询问u所在集合有多少颗树4.询问u，v是否在同一个集合分析：对于删除操作，只要新开一个点代替原来的点即可。#include<bits/stdc++.h>usingnamespacestd;constintmaxn=2e5+5e... 查看详情
数据结构--并查集的原理及实现(代码片段)
一，并查集的介绍 并查集（Union/Find）从名字可以看出，主要涉及两种基本操作:合并和查找。这说明，初始时并查集中的元素是不相交的，经过一系列的基本操作(Union)，最终合并成一个大的集合。而在某次合并之后，有一种... 查看详情
hdu2473junk-mailfilter(并查集的删除操作)
...来。。如今又做了做，还是没做出来。。、、这题涉及到并查集的删除操作。想到了设一个虚节点，可是我把虚节点设为了要删除的点的父节点。一直是栈溢出，目測是无限递归了。看了看别人的做法。原来仅仅要建一个映射就... 查看详情
hdu2473junk-mailfilter(并查集的删除操作)
ProblemDescriptionRecognizingjunkmailsisatoughtask.Themethodusedhereconsistsoftwosteps:1)Extractthecommoncharacteristicsfromtheincomingemail.2)Useafiltermatchingthesetofcommoncharacteristicsextractedt 查看详情
数据结构——并查集的详细解析和实现(代码片段)
...帮助、欢迎关注、点赞、收藏(一键三连)和订阅专栏哦一.并查集的定义1.并查集是一种树型的数据结构，用于处理一些不相交集合（disjointsets）的合并及查询问题。2.并查集通常包含两种操作查 查看详情
数据结构——并查集的详细解析和实现(代码片段)
...帮助、欢迎关注、点赞、收藏(一键三连)和订阅专栏哦一.并查集的定义1.并查集是一种树型的数据结构，用于处理一些不相交集合（disjointsets）的合并及查询问题。2.并查集通常包含两种操作查 查看详情
关于并查集的一切全在这里了(代码片段)
文章目录并查集初识「并查集」常用术语「并查集」基本思想「并查集」的两个实现方式QuickFind方式实现并查集QuickFind工作原理：代码实现与验证时间复杂度QuickUnion方式实现并查集QuickUnion的工作原理为什么QuickUnion比QuickFind... 查看详情
❤️数据结构入门❤️（2-5）-并查集
文章目录一、并查集的定义二、并查集的图解三、并查集的实现1、并查集的插入2、并查集的删除3、并查集的修改4、并查集的查找四、并查集的刷题实战一、并查集的定义二、并查集的图解三、并查集的实现1、并查集的插入2、... 查看详情
树的应用——并查集及实现代码(代码片段)
文章目录什么是并查集亲戚问题并查集的实现改进——路径压缩进一步改进——合并并查集的用途什么是并查集 并查集是一种树型的数据结构，用于处理一些不相交集合（disjointsets）的合并及查询问题。常常在使用... 查看详情
并查集的原理及实现(代码片段)
一、定义 并查集是一种树型的数据结构，用于处理一些不相交集合（DisjointSets）的合并及查询问题。二、代码实现 在并查集结构中，用一个pre[]数组来存储当前结点的父亲结点，有两个函数，found()函数用来寻找根结点，... 查看详情
数据结构-树并查集的定义及其操作(代码片段)
...化3查找操作4并操作1数据结构定义#defineMAX50intUFSets[MAX];//并查集2初始化//参数：并查集SvoidInit(intS[])inti;for(i=0;i<MAX;i++)S[i]=-1;【注】根结点可用来保存该子集合的元素个数（负数表示）。3查找操作寻找包... 查看详情
poj2236（并查集的应用）(代码片段)
WirelessNetworkTimeLimit: 10000MS MemoryLimit: 65536KTotalSubmissions: 35832 Accepted: 14863DescriptionAnearthquaketakesplaceinSoutheastAsia.TheACM(AsiaCooperatedMedicalt 查看详情
数据结构一篇文章学懂并查集+lrucache，拿来吧你！(代码片段)
并查集--LRUCache并查集的概念一、并查集的用途并查集的结构解释并查集的实现并查集相关习题习题1.leetcode朋友圈习题2.leetcode等式方程的可满足性并查集的思考与提升二、LRUCache的介绍1.什么是LRUCache习题.LRU缓存机制总结好文建... 查看详情
并查集的小节(代码片段)
寒假就看了并查集的视频，可是一直没怎么用了，现在终于还是拾起，看了这方面的视频还是很好理解的；看了挑战程序竞赛这本后，感觉大佬的思路就是简单，高效，可以首先写几个函数，分部实现各个功能，按照思路：1，... 查看详情
朋友(并查集的删除操作可看作是插入操作的逆序)
小z被选为他们村的村长，现在小z调查他们村上的关系。如果村民a和村民b是朋友，村民b和村民c是朋友，那么村民a和村民c也是朋友。那么村上的村民就会形成一个“朋友”团队，现在小z想知道他们村长有多少个这样的团队。同... 查看详情
restructuringcompany和almostunion-find并查集的区间合并与并查集的删除
RestructuringCompany Eventhemostsuccessfulcompanycangothroughacrisisperiodwhenyouhavetomakeaharddecision—torestructure,discardandmergedepartments,fireemployeesanddootherunpleasantstuff.Let‘sconsi 查看详情
算法笔记：并查集(代码片段)
1并查集介绍 并查集主要用于解决一些元素分组的问题。它管理一系列不相交的集合，并支持两种操作：合并（Union）：把两个不相交的集合合并为一个集合。查询（Find）：查询两个元素... 查看详情