# Leetcode01

**Repository Path**: weekend/leetcode01

## Basic Information

- **Project Name**: Leetcode01
- **Description**: No description available
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2026-03-26
- **Last Updated**: 2026-03-28

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README


## 并查集 Union-Find
- [x] [547. 省份数量](https://leetcode.cn/problems/number-of-provinces/description/)
- [x] [计算朋友圈](https://www.nowcoder.com/questionTerminal/a5c097f75db8418395b6a0e32c608c38)

### 并查集解决问题基本套路
1. 初始化集合结构，每个元素自成一个集合，设置其父节点为自身。`std::iota(city.begin(), city.end(), 0);`
2. 录入测试数据，开始合并集合 `merge(a, b)`
3. 合并时只对所有节点的根节点进行合并操作, `pa = find(a), pb = find(b); city[pb] = pa;`
4. 查找根节点的过程中顺便进行路径压缩，直到 `find(a) == a;`
5. 统计省份，需要再执行一次find进行路径压缩 `province_count.insert(find(city, i));`

## 带权并查集

## Kruskal最小生成树

## 完全子图 Clique
> Clique: a small group of people, with shared interests or other features in common, who spend time together and do not readily allow others to join them.

> 完全子图: 在一个图中，选出一些点，使得这些点之间“任意两点都有边相连”

### 极大完全子图 Maximal Clique
* A-B-C 形成三角形（3 人 clique）- 极大完全子图，也是最大完全子圈
* D-E 形成一条边（2 人 clique）- 极大完全子图
* 其中A-B 完全子图（2 人 clique），但是还可以加入C，所以不是极大

### Bron–Kerbosch 算法解决极大完全子图问题基本套路
> “Bron–Kerbosch” 这个名字来自两位提出算法的研究者：Coen Bron/Joep Kerbosch
> /brɔːn ˈkɛər-bɔːsk/（布朗·凯尔博斯克）

| 符号    | 常见理解                          | 含义               |
| ----- | ----------------------------- | ---------------- |
| **R** | **Result / Recursive clique** | 当前正在构造的 clique   |
| **P** | **Potential / Possible**      | 还能加入 clique 的候选点 |
| **X** | **eXcluded**                  | 已经排除 / 用过的点      |

```
BronKerbosch(R, P, X):
    if P 和 X 都为空:
        报告 R 为一个极大团
        return
    
    for P 中的每个顶点 v:
        BronKerbosch(R ∪ {v}, P ∩ N(v), X ∩ N(v))
        P := P \ {v}      // 从候选集中移除v
        X := X ∪ {v}      // 将v加入已排除集
```

## <algorithm> 集合
| 算法                         | 数学含义  | 作用   |
| -------------------------- | ----- | ---- |
| `set_intersection`         | A ∩ B | 交集   |
| `set_union`                | A ∪ B | 并集   |
| `set_difference`           | A - B | 差集   |
| `set_symmetric_difference` | A △ B | 对称差集 |

```cpp
// 交集 A ∩ B 两个集合都有的元素
set_intersection(A.begin(), A.end(),
                 B.begin(), B.end(),
                 back_inserter(res));

// 并集 A ∪ B 所有元素（去重）
set_union(A.begin(), A.end(),
          B.begin(), B.end(),
          back_inserter(res));

// 差集 A - B（只在 A 中的）
set_difference(A.begin(), A.end(),
               B.begin(), B.end(),
               back_inserter(res));

// 对称差 (A ∪ B) - (A ∩ B) 各自独有的元素
set_symmetric_difference(A.begin(), A.end(),
                         B.begin(), B.end(),
                         back_inserter(res));
```