下面浅学一些并查集的基本概念，然后再去实现思路——
简介：
一种树型的数据结构，用于处理一些不相交集合的合并及查询问题；
基础操作：
通常包括三个函数
| 函数 | 功能 |
|---|---|
| find(x) | 查找元素xxx属于哪个集合，也就是找当前元素所在树的根节点，查找的同时进行路径压缩 |
| union(a, b) | 合并元素aaa和元素bbb所属集合，根据树高合并两棵树 |
| isConnected(a, b) | 判断aaa和元素bbb是否处于同一集合中，也就是判断二者根是否相同 |
class Solution {
int[] p = new int[4010]; // 并查集数组，存父级节点
// 找当前节点的根
int find(int x) {
if(p[x] != x) // 非根节点
p[x] = find(p[x]); // 继续向下找根并进行路径压缩
return p[x];
}
// 连接两节点的根
void union(int a, int b) {
p[find(a)] = p[find(b)];
}
// 两节点是否连通
boolean isConnected(int a, int b) {
return find(a) == find(b);
}
public boolean possibleBipartition(int n, int[][] dislikes) {
for (int i = 1; i <= 2 * n; i++) // 节点+反向节点
p[i] = i; // 初始化并查集，指向自己
for (int[] cur : dislikes) {
int a = cur[0], b = cur[1];
if (isConnected(a, b)) // 连通，被迫在一组
return false;
// 利用反向节点维护连通关系
union(a, b + n);
union(b, a + n);
}
return true;
}
}
union会和C++中的预定义函数重名class Solution {
public:
int p[4010]; // 并查集数组，存父级节点
// 找当前节点的根
int find(int x) {
if(p[x] != x) // 非根节点
p[x] = find(p[x]); // 继续向下找根并进行路径压缩
return p[x];
}
// 连接两节点的根
void unionn(int a, int b) {
p[find(a)] = p[find(b)];
}
// 两节点是否连通
bool isConnected(int a, int b) {
return find(a) == find(b);
}
bool possibleBipartition(int n, vector<vector<int>>& dislikes) {
for (int i = 1; i <= 2 * n; i++) // 节点+反向节点
p[i] = i; // 初始化并查集，指向自己
for (auto cur : dislikes) {
int a = cur[0], b = cur[1];
if (isConnected(a, b)) // 连通，被迫在一组
return false;
// 利用反向节点维护连通关系
unionn(a, b + n);
unionn(b, a + n);
}
return true;
}
};
DFS(node, clr)函数表示将节点node染成clr色class Solution {
int N = 2010, M = 2 * 10010;
int[] head = new int[N], edge = new int[M], next = new int[M];
int[] color = new int[N];
int idx = 0;;
void add(int a, int b) {
edge[idx] = b;
next[idx] = head[a];
head[a] = idx++;
}
boolean DFS(int node, int clr) {
color[node] = clr;
for (int i = head[node]; i != -1; i = next[i]) {
int j = edge[i];
// 不喜欢双方同色
if (color[j] == clr)
return false;
if (color[j] == 0 && !DFS(j, 3 - clr))
return false;
}
return true;
}
public boolean possibleBipartition(int n, int[][] dislikes) {
Arrays.fill(head, -1);
for (int[] cur : dislikes) { // 构建无向图
int a = cur[0], b = cur[1];
add(a, b);
add(b, a);
}
for (int i = 1; i <= n; i++) {
if (color[i] != 0) // 已经染过
continue;
if (!DFS(i, 1)) // 无法染色成功
return false;
}
return true;
}
}
class Solution {
public:
static const int N = 2010, M = 2 * 10010;
int head[N], edge[M], next[M];
int color[N];
int idx = 0;;
void add(int a, int b) {
edge[idx] = b;
next[idx] = head[a];
head[a] = idx++;
}
bool DFS(int node, int clr) {
color[node] = clr;
for (int i = head[node]; i != -1; i = next[i]) {
int j = edge[i];
// 不喜欢双方同色
if (color[j] == clr)
return false;
if (color[j] == 0 && !DFS(j, 3 - clr))
return false;
}
return true;
}
bool possibleBipartition(int n, vector<vector<int>>& dislikes) {
memset(head, -1, sizeof(head));
for (auto cur : dislikes) { // 构建无向图
int a = cur[0], b = cur[1];
add(a, b);
add(b, a);
}
for (int i = 1; i <= n; i++) {
if (color[i] != 0) // 已经染过
continue;
if (!DFS(i, 1)) // 无法染色成功
return false;
}
return true;
}
};
算法题就回避一下Rust……待我学成归来……
填了拖了好久的并查集的坑还捎带复习了一波链式前向星存图；
感觉链式前向星忘得差不多了……
