并查集连通分量

$images\cherry_red.png$ 1 Leetcodegaogaotwo

$images\cherry_blue.png$ 1.1 链表

$images\cherry_orange.png$ 1.1.1 分割链表

$images\cherry_orange.png$ 1.1.2 反转链表

$images\cherry_orange.png$ 1.1.3 快慢指针链表的中间节点

$images\cherry_orange.png$ 1.1.4 链表的倒数第k个节点

$images\cherry_orange.png$ 1.1.5 回文链表

$images\cherry_orange.png$ 1.1.6 链表的删除

$images\cherry_orange.png$ 1.1.7 链表反转2

$images\cherry_orange.png$ 1.1.8 链表的第一个相交节点

$images\cherry_blue.png$ 1.2 dfs

$images\cherry_orange.png$ 1.2.1 岛屿数量

$images\cherry_orange.png$ 1.2.2 机器人的运动范围

$images\cherry_orange.png$ 1.2.3 字符串的全排列(回溯算法)

$images\cherry_orange.png$ 1.2.4 判断一个数字是否可以表示成三的幂的和

$images\cherry_orange.png$ 1.2.5 不同路径III dfs+回溯

$images\cherry_orange.png$ 1.2.6 组合总和 dfs+回溯

$images\cherry_orange.png$ 1.2.7 子集 dfs or 状态枚举

$images\cherry_blue.png$ 1.3 bfs

$images\cherry_blue.png$ 1.4 双指针

$images\cherry_orange.png$ 1.4.1 奇数在前，偶数在后

$images\cherry_blue.png$ 1.5 二维矩阵的前缀和

$images\cherry_orange.png$ 1.5.1 1074. 元素和为目标值的子矩阵数量

$images\cherry_orange.png$ 1.5.2 304. 二维区域和检索 - 矩阵不可变

$images\cherry_blue.png$ 1.6 数组变化

$images\cherry_orange.png$ 1.6.1 大数加减法

$images\cherry_orange.png$ 1.6.2 717. 1 比特与 2 比特字符

$images\cherry_blue.png$ 1.7 排序算法

$images\cherry_orange.png$ 1.7.1 把数组排成最小的数

$images\cherry_orange.png$ 1.7.2 根据字符出现的次数频率进行排序

$images\cherry_orange.png$ 1.7.3 最大数

$images\cherry_orange.png$ 1.7.4 969. 煎饼排序

$images\cherry_blue.png$ 1.8 dp动态规划

$images\cherry_orange.png$ 1.8.1 斐波那契数列

$images\cherry_orange.png$ 1.8.2 俄罗斯套娃信封问题

$images\cherry_orange.png$ 1.8.3 分割回文串

$images\cherry_orange.png$ 1.8.4 01背包

$images\cherry_orange.png$ 1.8.5 打家劫舍II

$images\cherry_orange.png$ 1.8.6 青蛙过河

$images\cherry_orange.png$ 1.8.7 最长回文子串

$images\cherry_orange.png$ 1.8.8 目标和（01背包）

$images\cherry_orange.png$ 1.8.9 最大子序和

$images\cherry_blue.png$ 1.9 滑动窗口

$images\cherry_orange.png$ 1.9.1 绝对差不超过限制的最长连续子数组

$images\cherry_orange.png$ 1.9.2 三数之和

$images\cherry_blue.png$ 1.10 二叉树性质

$images\cherry_orange.png$ 1.10.1 二叉树的最小深度

$images\cherry_orange.png$ 1.10.2 二叉树的层次遍历

$images\cherry_orange.png$ 1.10.3 二叉树的镜像翻转

$images\cherry_orange.png$ 1.10.4 二叉树的最大深度

$images\cherry_orange.png$ 1.10.5 二叉搜索树节点最小距离

$images\cherry_orange.png$ 1.10.6 二叉树重构从小到达按照->right情况

$images\cherry_orange.png$ 1.10.7 二叉搜索数的范围和

$images\cherry_orange.png$ 1.10.8 N叉树的前序遍历

$images\cherry_blue.png$ 1.11 递归

$images\cherry_orange.png$ 1.11.1 1+2...+n

$images\cherry_blue.png$ 1.12 并查集

$images\cherry_orange.png$ 1.12.1 并查集连通分量

$images\cherry_orange.png$ 1.12.2 并查集城市连通

$images\cherry_blue.png$ 1.13 堆栈

$images\cherry_orange.png$ 1.13.1 通过队列来实现栈

$images\cherry_orange.png$ 1.13.2 下一个更大元素 II

$images\cherry_orange.png$ 1.13.3 删除字符串中的所有相邻重复项

$images\cherry_orange.png$ 1.13.4 基本计算机

$images\cherry_orange.png$ 1.13.5 计算机

$images\cherry_orange.png$ 1.13.6 逆波兰表达式

$images\cherry_orange.png$ 1.13.7 接雨水

$images\cherry_orange.png$ 1.13.8 柱状图中最大矩形面积

$images\cherry_orange.png$ 1.13.9 反转每对括号间的子串

$images\cherry_blue.png$ 1.14 队列（or 优先队列）

$images\cherry_orange.png$ 1.14.1 最大平均通过率

$images\cherry_orange.png$ 1.14.2 最大的团队表现值

$images\cherry_orange.png$ 1.14.3 找出第K大的异或坐标值

$images\cherry_orange.png$ 1.14.4 1.2滑动窗口的最大值

$images\cherry_orange.png$ 1.14.5 二叉搜索数的范围和

$images\cherry_orange.png$ 1.14.6 员工的重要性

$images\cherry_blue.png$ 1.15 Hash查询匹配

$images\cherry_orange.png$ 1.15.1 猜灯谜

$images\cherry_orange.png$ 1.15.2 720. 词典中最长的单词

$images\cherry_blue.png$ 1.16 前缀树

$images\cherry_orange.png$ 1.16.1 实现Trie(前缀树)

$images\cherry_orange.png$ 1.16.2 添加与搜索单词 - 数据结构设计

$images\cherry_blue.png$ 1.17 位运算

$images\cherry_orange.png$ 1.17.1 比特位计数

$images\cherry_orange.png$ 1.17.2 不用加减乘除做加法

$images\cherry_orange.png$ 1.17.3 可被 5 整除的二进制前缀

$images\cherry_orange.png$ 1.17.4 汉明距离总和

$images\cherry_blue.png$ 1.18 二分法

$images\cherry_orange.png$ 1.18.1 在D天内送达包裹的能力

$images\cherry_orange.png$ 1.18.2 第一个错误的版本

$images\cherry_blue.png$ 1.19 数据结构性质

$images\cherry_blue.png$ 1.20 回溯法思想

$images\cherry_blue.png$ 1.21 字符串处理(模拟)

$images\cherry_orange.png$ 1.21.1 Excel 表列序号进制转换

$images\cherry_orange.png$ 1.21.2 838.推多米诺

$images\cherry_blue.png$ 1.22 模拟

$images\cherry_blue.png$ 1.23 数学定理

$images\cherry_orange.png$ 1.23.1 1828. 统计一个圆中点的数目

1319. 连通网络的操作次数
用以太网线缆将 n 台计算机连接成一个网络，计算机的编号从 0 到 n-1。线缆用 connections 表示，其中 connections[i] = [a, b] 连接了计算机 a 和 b。

网络中的任何一台计算机都可以通过网络直接或者间接访问同一个网络中其他任意一台计算机。

给你这个计算机网络的初始布线 connections，你可以拔开任意两台直连计算机之间的线缆，并用它连接一对未直连的计算机。请你计算并返回使所有计算机都连通所需的最少操作次数。如果不可能，则返回 -1 。

示例 1：

输入：n = 4, connections = [[0,1],[0,2],[1,2]]
输出：1
解释：拔下计算机 1 和 2 之间的线缆，并将它插到计算机 1 和 3 上。
示例 2：

输入：n = 6, connections = [[0,1],[0,2],[0,3],[1,2],[1,3]]
输出：2
示例 3：

输入：n = 6, connections = [[0,1],[0,2],[0,3],[1,2]]
输出：-1
解释：线缆数量不足。
示例 4：

输入：n = 5, connections = [[0,1],[0,2],[3,4],[2,3]]
输出：0

提示：

1 <= n <= 10^5
1 <= connections.length <= min(n*(n-1)/2, 10^5)
connections[i].length == 2
0 <= connections[i][0], connections[i][1] < n
connections[i][0] != connections[i][1]
没有重复的连接。
两台计算机不会通过多条线缆连接。

$images\30-1.png$

class Solution {
public:
    int f[100001];

int Find(int x){
/*连通
    return f[x]==x?x:f[x]=Find(f[x]);
*/
        int ret=x;
        while(ret!=f[ret]){
            ret=f[ret];
        }
/*路径压缩*/
    int j=x,i;
    while(j!=ret){
        i=f[j];
        f[j]=ret;;
        j=i;
    }
    return ret;
}
    int makeConnected(int n, vector<vector<int>>& g) {
        if(g.size()<n-1) return -1;
        for(int i=0;i<n;++i) f[i]=i;

        for(int i=0;i<g.size();++i) {
            int a=Find(g[i][0]),b=Find(g[i][1]);
            if(a!=b) f[a]=b;
        }
        int cnt=0;
        for(int i=0;i<n;++i) cnt+=(i==Find(i));
        return cnt-1;
    }
};