关键词：
主要还是看find的join俩个操作,测试数据
1
6
1 2
4 3
1 3
5 6
6 1
7 1
#include <iostream> #include <stdio.h> #include <memory.h> using namespace std; /** * 并查集判断有几个联通子图 */ const int maxN = 20; int a[maxN]; int find(int key); void join(int s, int e); void _init(); int main() { freopen("d:\3.txt", "r", stdin); int c; cin >> c; int cc = c; while (c--) { cout << "case:" << cc - c << endl; int n; int s, e; cin >> n; int maxNode = -1; int node[maxN]; memset(node, 0, sizeof(node)); _init(); for (int i = 0; i < n; i++) { cin >> s >> e; node[s] = 1; node[e] = 1; maxNode = maxNode > s ? maxNode : s; maxNode = maxNode > e ? maxNode : e; join(s, e); } int head[maxN]; int maxP = -1; memset(head, 0, sizeof(head)); int total = 0; for (int i = 0; i <= maxNode; i++) { if (!node[i]) continue; int p = find(i); maxP = maxP > p ? maxP : p; head[p] = 1; } for (int i = 0; i <= maxP; i++) { if (head[i] == 0) continue; total++; cout << "map" << total << " = "; for (int j = 0; j <= maxNode; j++) { if (!node[i]) continue; int p = find(j); if (p == i) { cout << " " << j; } } cout << endl; } cout << "total map=" << total << endl << endl; } return 0; } int find(int key) { return key == a[key] ? key : a[key] = find(a[key]); } void join(int s, int e) { int p1 = find(s); int p2 = find(e); if (p1 != p2) { if (p1 >= p2) a[p1] = p2; else a[p2] = p1; } } void _init() { for (int i = 0; i < maxN; i++) a[i] = i; }
有错请评论
并查集
带偏移量的并查集讲解Butterfly AC代码 第二种AC代码1182:食物链 AC代码 查看详情
thesuspects（并查集）
个人心得：最基础的并查集经典题。借此去了解了一下加深版的即加权并查集，比如食物链的题目，这种题目实行起来还是有一定的难度，不仅要找出与父节点的关系，还要在路径压缩的时候进行更新，这一点现在还是没那么上... 查看详情
一道神奇的并查集
#include<cstdio>#include<cstring>#include<cmath>#include<algorithm>usingnamespacestd;template<classT>inlinevoidread(T&_a){boolf=0;int_ch=getchar();_a=0;while(_ch<‘ 查看详情
可持久化并查集
可持久化并查集题目链接https://www.luogu.org/problemnew/show/P3402（据说这题暴力随便水）思路首先明确一点，本题考得不是并查集，而是可持久化跟并查集没啥关系。而且在这道题中用不带路径压缩的并查集（欢迎推翻这个flag）然后... 查看详情
杭电1213题解：一道最基础的并查集问题
ProblemDescriptionTodayisIgnatius‘birthday.Heinvitesalotoffriends.Nowit‘sdinnertime.Ignatiuswantstoknowhowmanytablesheneedsatleast.Youhavetonoticethatnotallthefriendsknoweachother,andallthefriendsdono 查看详情
uvalive6910cuttingtree（并查集应用）
...的方法也能做出来。 我第一次使用的是不合并路径的并查集，几乎是一种暴力，花了600多MS，感觉还是不太好的，发现AC的人很多都在300MS之内的过得。 看到他们的做法后，我知道了这个题比较好的做法。 逆向思维的... 查看详情
裸的并查集poj1611thesuspects
http://poj.org/problem?id=1611【Accepted】1#include<iostream>2#include<cstdio>3#include<algorithm>4#include<cstring>5#include<string>6usingnamespacestd;7constintmaxn=3e4+3; 查看详情
几道莫名ac的并查集题
...天还是做（看）差分约束的，但是上不去Vjudge我只能来刷并查集了。%%%静萱大佬把那么多年的noip题都刷遍了，我只能刷水题，noip的题实在是太难了不会啊。 第一道：洛谷P2024食物链 虽然说我很不喜欢看别人代码，但是... 查看详情
algorithmsiv带权重的并查集算法
问题普通的Union-find并查集算法没有加入权重, 可以构造特别的输入使得每次合并的时候高的树HighTree以低的树LowTree的根【root(LowTree)】为新的根, 造成树的不平衡，从而使得效率下降。 用一个新的数组标记节点当前的... 查看详情
uva11987带删除的并查集
...合中3p输出p元素集合的个数及全部元素的和。 题解：并查集。只是并查集中并没有删除的操作。所以就需要将删除的这个点的影响降到0，也就是给删除的点申请一个新的id，以后都是用这个新的id来表示这个点，这样原来的... 查看详情
并查集2——带权并查集
路径压缩前面的并查集的复杂度实际上有些极端情况会很慢。比如树的结构正好是一条链，那么最坏情况下，每次查询的复杂度达到了 O(n)。路径压缩 的思想是，我们只关心每个结点的父结点，而并不太关心树的真正的... 查看详情
加权并查集
加权并查集是一种特殊的并查集，除可提供查询操作外，还可用于表示元素与其代表元素的关系。下面以食物链为例，讲解一下加权并查集。#include<cstdio>//调用cstdio库，使用getchar函数#include<cctype>//调用cctype库，使... 查看详情
并查集(入门)(代码片段)
首先先看一道很简单的并查集的题目：https://vjudge.net/contest/297398#problem/A这道题就是让你判断两两城镇之间是否联通 如果不联通就要修建一条道路 就我的理解来说，如果单独使用并查集就是为了合并有相同根结点(或者理... 查看详情
uva11987almostunion-find（支持删除操作的并查集）
传送门DescriptionIhopeyouknowthebeautifulUnion-Findstructure.Inthisproblem,you’retoimplementsomethingsimilar,butnotidentical.Thedatastructureyouneedtowriteisalsoacollectionofdisjointsets,supporting 查看详情
有点意思的并查集(代码片段)
K-HowManyAnswersAreWrong HDU-3038题目大意：两个人玩游戏，一个人说一个区间内的数的和，然后判断她说的有多少句和之前说过的冲突的。一开始想的用一个数就代表他到根节点里的数和，但是在路径压缩时明显不对，因为已知[1,8... 查看详情
关于并查集的一切全在这里了(代码片段)
文章目录并查集初识「并查集」常用术语「并查集」基本思想「并查集」的两个实现方式QuickFind方式实现并查集QuickFind工作原理：代码实现与验证时间复杂度QuickUnion方式实现并查集QuickUnion的工作原理为什么QuickUnion比QuickFind... 查看详情
并查集
...算：交、并、补、差，判定一个元素是否属于某一集合。并查集：集合并、查某元素属于哪个集合。并查集问题中集合存储如何实现？1）可以用树结构表示集合，树的每个结点就是集合中的各个元素。2）采用数组的形式进行存... 查看详情
可以删点的并查集
如题。方法一：LCT！细节挺多，略。方法二：如题（废话。。）如果照传统的方法，比如1，2，3在一起要把1删掉，要保证1的爸爸和2，3以后不一样，如果1不是根节点就直接$fa[1]=1$，否则需要改所有的儿子。上面的问题在于删掉... 查看详情