算法.图论-习题全集(Updating)
文章目录
- 本节设置的意义
- 并查集篇
- 并查集简介以及常见技巧
- 并查集板子(洛谷)
- 情侣牵手问题
- 相似的字符串组
- 岛屿数量(并查集做法)
- 省份数量
- 移除最多的同行或同列石头
- 最大的人工岛
- 找出知晓秘密的所有专家
- 建图及其拓扑排序篇
- 链式前向星建图板子
- 课程表
本节设置的意义
主要就是为了复习图论算法, 尝试从题目解析的角度,更深入的理解图论算法…
并查集篇
并查集简介以及常见技巧
并查集是一种用于大集团查找, 合并等操作的数据结构, 常见的方法有
find: 用来查找元素在大集团中的代表元素(这里使用的是扁平化的处理)isSameSet: 用来查找两个元素是不是一个大集团的(其实就是find的应用)union: 用来合并两大集团的元素
关于并查集打标签的技巧, 其实我们之前的size数组也是一种打标签的逻辑, 其实打标签就是给每一个集团的代表节点打上标签即可, 还有我们在并查集的题目中通常会设置一个sets作为集合的总数目(每次合并–), 这是一个常见的技巧, 并查集的细节我们在这里不进行过多的介绍, 在之前的章节中有细致的描述…
并查集板子(洛谷)
这里我们的并查集的板子使用的是洛谷的板子(小挂大的优化都没必要其实)
// 并查集模版(洛谷)
// 本实现用递归函数实现路径压缩，而且省掉了小挂大的优化，一般情况下可以省略
// 测试链接 : https://www.luogu.com.cn/problem/P3367
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
public class Main{
public static int MAXN = 10001;
public static int[] father = new int[MAXN];
public static int n;
public static void build() {
for (int i = 0; i <= n; i++) {
father[i] = i;
}
}
public static int find(int i) {
if (i != father[i]) {
father[i] = find(father[i]);
}
return father[i];
}
public static boolean isSameSet(int x, int y) {
return find(x) == find(y);
}
public static void union(int x, int y) {
father[find(x)] = find(y);
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StreamTokenizer in = new StreamTokenizer(br);
PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
while (in.nextToken() != StreamTokenizer.TT_EOF) {
n = (int) in.nval;
build();
in.nextToken();
int m = (int) in.nval;
for (int i = 0; i < m; i++) {
in.nextToken();
int z = (int) in.nval;
in.nextToken();
int x = (int) in.nval;
in.nextToken();
int y = (int) in.nval;
if (z == 1) {
union(x, y);
} else {
out.println(isSameSet(x, y) ? "Y" : "N");
}
}
}
out.flush();
out.close();
br.close();
}
}
情侣牵手问题
本题的突破点就是如果一个大集团里面有 n 对情侣, 那么我们至少要交换 n - 1次(通过把情侣进行编号)
// 这次我们尝试使用轻量版的并查集来解决这道题
class Solution {
private static final int MAX_CP = 31;
private static final int[] father = new int[MAX_CP];
private static int sets = 0;
private static int find(int i) {
if (i != father[i]) {
father[i] = find(father[i]);
}
return father[i];
}
private static boolean isSameSet(int a, int b) {
return find(a) == find(b);
}
private static void union(int a, int b) {
int fa = find(a);
int fb = find(b);
if (fa != fb) {
father[fa] = fb;
sets--;
}
}
// 初始化并查集
private static void build(int n) {
for (int i = 0; i < n; i++) {
father[i] = i;
}
sets = n;
}
public int minSwapsCouples(int[] row) {
build(row.length / 2);
for (int i = 0; i < row.length; i += 2) {
int n1 = row[i] / 2;
int n2 = row[i + 1] / 2;
union(n1, n2);
}
return row.length / 2 - sets;
}
}
相似的字符串组
其实就是枚举每一个位置, 然后判断是不是一组的就OK了
// 还是使用一下轻量级的并查集板子
class Solution {
private static final int MAX_SZ = 301;
private static final int[] father = new int[MAX_SZ];
private static int sets = 0;
private static int find(int i) {
if (i != father[i]) {
father[i] = find(father[i]);
}
return father[i];
}
private static boolean isSameSet(int a, int b) {
return find(a) == find(b);
}
private static void union(int a, int b) {
int fa = find(a);
int fb = find(b);
if (fa != fb) {
father[fa] = fb;
sets--;
}
}
// 初始化并查集
private static void build(int n) {
for (int i = 0; i < n; i++) {
father[i] = i;
}
sets = n;
}
public int numSimilarGroups(String[] strs) {
build(strs.length);
// 主流程的时间复杂度是 O(n ^ 2), 遍历strs的每一个位置
int m = strs[0].length();
for (int i = 0; i < strs.length; i++) {
for (int j = i + 1; j < strs.length; j++) {
// 获取到两个字符串, 然后计算两个字符串的不同字符数量
String s1 = strs[i];
String s2 = strs[j];
int diff = 0;
for (int k = 0; k < m && diff < 3; k++) {
if (s1.charAt(k) != s2.charAt(k))
diff++;
}
if (diff == 0 || diff == 2)
union(i, j);
}
}
return sets;
}
}
岛屿数量(并查集做法)
这道题的解法非常多, 比如多源 BFS , 洪水填充(其实就是递归加回溯) , 还有今天介绍的并查集的方法(这个方法不是最好的)
// 这个题的并查集做法只要注意一点就可以了: 把一个二维下标转化为一维下标
class Solution {
private static final int MAX_SZ = 301 * 301;
private static final int[] father = new int[MAX_SZ];
private static int sets = 0;
private static int row = 0;
private static int col = 0;
// 模拟bfs的move数组
private static final int[] move = { -1, 0, 1, 0, -1 };
private static int find(int i) {
if (i != father[i]) {
father[i] = find(father[i]);
}
return father[i];
}
private static boolean isSameSet(int a, int b) {
return find(a) == find(b);
}
private static void union(int a, int b) {
int fa = find(a);
int fb = find(b);
if (fa != fb) {
father[fa] = fb;
sets--;
}
}
private static void build(char[][] grid, int rl, int cl) {
row = rl;
col = cl;
sets = 0;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (grid[i][j] == '1') {
sets++;
father[getIndex(i, j)] = getIndex(i, j);
}
}
}
}
public int numIslands(char[][] grid) {
// 初始化并查集并统计 '1' 的数量
build(grid, grid.length, grid[0].length);
// 遍历grid进行合并
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
// 向四个方向扩展
if (grid[i][j] == '1') {
for (int k = 0; k < 4; k++) {
int nx = i + move[k];
int ny = j + move[k + 1];
if (nx >= 0 && nx < row && ny >= 0 && ny < col && grid[nx][ny] == '1') {
union(getIndex(i, j), getIndex(nx, ny));
}
}
}
}
}
return sets;
}
// 二维下标转一维下标
private static int getIndex(int i, int j) {
return i * col + j;
}
}
省份数量
没什么可说的, 就是一个简单的并查集的思路
class Solution {
// 这其实也是一个并查集的题
private static final int MAXM = 201;
private static final int[] father = new int[MAXM];
private static final int[] size = new int[MAXM];
private static int sets = 0;
private static int find(int i){
if(i != father[i]){
father[i] = find(father[i]);
}
return father[i];
}
private static boolean isSameSet(int a, int b){
return find(a) == find(b);
}
private static void union(int a, int b){
if(!isSameSet(a, b)){
int fa = find(a);
int fb = find(b);
if(size[fa] > size[fb]){
father[fb] = fa;
size[fa] += size[fb];
}else{
father[fa] = fb;
size[fb] += size[fa];
}
sets--;
}
}
private static void build(int n){
for(int i = 0; i < n; i++){
father[i] = i;
size[i] = 1;
}
sets = n;
}
public int findCircleNum(int[][] isConnected) {
// 初始化并查集
build(isConnected.length);
for(int i = 0; i < isConnected.length; i++){
int[] info = isConnected[i];
for(int j = 0; j < info.length; j++){
if(info[j] == 1){
union(i, j);
}
}
}
return sets;
}
}
移除最多的同行或同列石头
其实就是每一个集团最后都会被消成一个元素, 我们中间用哈希表加了一些关于离散化的处理的技巧
// 使用一下轻量版本的并查集加上哈希表进行离散化的操作
class Solution {
private static Map<Integer, Integer> rowFirst = new HashMap<>();
private static Map<Integer, Integer> colFirst = new HashMap<>();
private static final int MAXM = 1001;
private static final int[] father = new int[MAXM];
private static int sets = 0;
private static int find(int i){
if(i != father[i]){
father[i] = find(father[i]);
}
return father[i];
}
private static boolean isSameSet(int a, int b){
return find(a) == find(b);
}
private static void union(int a, int b){
int fa = find(a);
int fb = find(b);
if(fa != fb){
father[fa] = fb;
sets--;
}
}
// 初始化并查集
private static void build(int n){
for(int i = 0; i < n; i++){
father[i] = i;
}
sets = n;
}
public int removeStones(int[][] stones) {
// 清空哈希表
rowFirst.clear();
colFirst.clear();
// 初始化并查集
build(stones.length);
for(int i = 0; i < stones.length; i++){
int row = stones[i][0];
int col = stones[i][1];
if(!rowFirst.containsKey(row)){
rowFirst.put(row, i);
}else{
union(rowFirst.get(row), i);
}
if(!colFirst.containsKey(col)){
colFirst.put(col, i);
}else{
union(colFirst.get(col), i);
}
}
return stones.length - sets;
}
}
最大的人工岛
本题注意的点就是, 首先我们二维的矩阵, 想要使用并查集, 需要先把二维的坐标转化为一维的坐标, 然后通过一维的坐标使用并查集, 首先把所有的岛进行合并, 然后来到一个 空位置 , 就尝试向四个方向进行扩展尝试进行岛屿的链接, 最后返回最大的连成一片的岛屿数量即可
/**
* 本题我们是采用的并查集(轻量板子)的方法来做
* 核心点就是首先使用 并查集 (二维下标转换一维下标) 进行人工岛的合并
* 本题需要我们使用size的辅助信息, 因为 size 也相当于打标签的技巧
* 然后枚举每一个位置进行岛屿的合并
*/
class Solution {
private static final int MAX_LEN = 501;
private static final int MAX_SIZE = MAX_LEN * MAX_LEN;
private static final int[] father = new int[MAX_SIZE];
private static final int[] size = new int[MAX_SIZE];
private static int len = 0;
private static final int[] move = {-1, 0, 1, 0, -1};
private static int find(int i){
if(i != father[i]){
father[i] = find(father[i]);
}
return father[i];
}
private static boolean isSameSet(int a, int b){
return find(a) == find(b);
}
private static void union(int a, int b){
if(!isSameSet(a, b)){
int fa = find(a);
int fb = find(b);
if(size[fa] > size[fb]){
father[fb] = fa;
size[fa] += size[fb];
}else{
father[fa] = fb;
size[fb] += size[fa];
}
}
}
// 初始化并查集
private static void build(int[][] grid){
len = grid.length;
for(int i = 0; i < len; i++){
for(int j = 0; j < len; j++){
if(grid[i][j] == 1){
int index = getIndex(i, j);
father[index] = index;
size[index] = 1;
}
}
}
}
// 二维下标转换为一维下标
private static int getIndex(int i, int j){
return i * len + j;
}
public int largestIsland(int[][] grid) {
build(grid);
int res = 0;
// 遍历矩阵进行合并
for(int i = 0; i < len; i++){
for(int j = 0; j < len; j++){
if(grid[i][j] == 1){
// 此时向四周进行扩展合并
for(int k = 0; k < 4; k++){
int nx = i + move[k];
int ny = j + move[k + 1];
if(nx >= 0 && nx < len && ny >= 0 && ny < len && grid[nx][ny] == 1){
union(getIndex(i, j), getIndex(nx, ny));
}
}
// 尝试进行人工岛最大面积的更新
res = Math.max(res, size[find(getIndex(i, j))]);
}
}
}
// 遍历所有的 0 位置, 尝试向四周进行枚举更新最大值
// 创建一个map用来进行去重
Set<Integer> set = new HashSet<>();
for(int i = 0; i < len; i++){
for(int j = 0; j < len; j++){
if(grid[i][j] == 0){
set.clear();
int tempRes = 1;
// 向四周进行扩展然后尝试进行岛屿链接
for(int k = 0; k < 4; k++){
int nx = i + move[k];
int ny = j + move[k + 1];
if(nx >= 0 && nx < len && ny >= 0 && ny < len && grid[nx][ny] == 1){
int f = find(getIndex(nx, ny));
if(!set.contains(f)){
tempRes += size[f];
set.add(f);
}
}
}
res = Math.max(res, tempRes);
}
}
}
return res;
}
}
找出知晓秘密的所有专家
本题我们运用的是一种打标签的技巧, 还有就是注意的是并查集如何进行拆解, 其实就是修改一下father数组的内容, 然后把size数组的值置为1即可
/**
* 本题主要就是涉及到并查集的打标签的技巧, 还有如何拆散一个并查集
* 首先就是关于并查集打标签: 其实就是给集团领袖节点打上标签信息(类似size数组)
* 关于拆散并查集: 其实就是把father数组重新设置为自身, size置为1(如果有的话)
*/
class Solution {
// 并查集轻量化的板子
private static final int MAXN = 100001;
private static final int[] father = new int[MAXN];
private static final boolean[] knowSecrets = new boolean[MAXN];
private static int find(int i){
if(i != father[i]){
father[i] = find(father[i]);
}
return father[i];
}
private static boolean isSameSet(int a, int b){
return find(a) == find(b);
}
private static void union(int a, int b){
if(!isSameSet(a, b)){
father[find(a)] = find(b);
}
}
// 初始化并查集
private static void build(int n, int firstPerson){
for(int i = 0; i < n; i++){
father[i] = i;
knowSecrets[i] = false;
}
// 初始化知道秘密的集团(只需要给领袖节点打上标签就好了)
union(0, firstPerson);
knowSecrets[0] = true;
knowSecrets[firstPerson] = true;
}
public List<Integer> findAllPeople(int n, int[][] meetings, int firstPerson) {
// 首先初始化并查集
build(n, firstPerson);
// 把meetings进行排序便于处理
Arrays.sort(meetings, (a, b) -> a[2] - b[2]);
int l = 0;
int r = 0;
while(l < meetings.length){
// 首先把r指针置为l的位置
r = l;
int tempL = l;
// 向右侧扩充(结束的时候r指向的下一个不同的元素的边界位置)
while(r < meetings.length && meetings[r][2] == meetings[l][2]){
r++;
}
// 先便利一边并查集进行集合元素的合并
while(l < r){
union(meetings[l][0], meetings[l][1]);
if(isSameSet(0, meetings[l][0])) knowSecrets[meetings[l][0]] = true;
if(isSameSet(0, meetings[l][1])) knowSecrets[meetings[l][1]] = true;
l++;
}
// 再次便利一边这个时间点的元素进行集合的拆解
l = tempL;
while(l < r){
if(!isSameSet(meetings[l][0], 0) && !isSameSet(meetings[l][1], 0)){
father[meetings[l][0]] = meetings[l][0];
father[meetings[l][1]] = meetings[l][1];
}
l++;
}
l = r;
}
// 进行元素的收集
List<Integer> res = new ArrayList<>();
for(int i = 0; i < n; i++){
if(isSameSet(0, i)){
res.add(i);
}
}
return res;
}
}
建图及其拓扑排序篇
建图的方法有三种, 邻接表, 邻接矩阵, 以及链式前向星, 我们更推荐的是静态空间的链式前向星的建图法, 下面是链式前向星的板子
链式前向星建图板子
/**
* 关于大厂笔试以及比赛中的建图方式的测试, 其实就是使用静态的数组空间进行建图
* 我们设置 3 / 4 / 5 个静态数组空间
* head数组(存储点对应的头边编号), next数组(边对应下一条边的编号), to数组(边去往的点), weight数组(边对应的权值), indegree数组(点对应的入度)
* 关于拓扑排序(topoSort), 我们最常用的方法其实就是零入度删除法(使用队列, 必要的时候使用小根堆), 关于是否环化的判断我们使用计数器实现
* 下面是我们提供的链式建图的板子, 以及拓扑排序的板子
*/
public class createGraphByLinkedProStar{
// 设置点的最大数量
private static final int MAXN = 10001;
// 设置边的最大数量
private static final int MAXM = 10001;
// head数组
private static final int[] head = new int[MAXN];
// next数组
private static final int[] next = new int[MAXM];
// to数组
private static final int[] to = new int[MAXM];
// weight数组
private static final int[] weight = new int[MAXM];
// indegree数组(统计入度)
private static final int[] indegree = new int[MAXN];
// cnt统计边的数量
private static int cnt = 1;
// 添加边的方法(顺便统计入度)
private static void addEdge(int u, int v, int w){
next[cnt] = head[u];
to[cnt] = v;
weight[cnt] = w;
head[u] = cnt++;
indegree[v]++;
}
// 初始化静态空间(只需要清空head以及indegree数组)然后建图(这里是有向带权图)
private static void build(int n, int[][] edges){
cnt = 1;
for(int i = 0; i <= n; i++){
indegree[i] = 0;
head[i] = 0;
}
for(int[] edge : edges){
addEdge(edge[0], edge[1], edge[2]);
}
}
// 拓扑排序(topoSort的板子)
private static int[] topoSort(int n){
// 首先创建一个队列(将来可以作为结果返回)
int[] queue = new int[n];
int l = 0;
int r = 0;
// 遍历入度表, 添加所有0入度的点进队列
for(int i = 0; i < n; i++){
if(indegree[i] == 0){
queue[r++] = i;
}
}
// 利用链式前向星的遍历开始跑拓扑排序
int elemCnt = 0;
while(l < r){
int cur = queue[l++];
elemCnt++;
for(int ei = head[cur]; ei != 0; ei = next[ei]){
if(--indegree[to[ei]] == 0){
queue[r++] = to[ei];
}
}
}
return elemCnt == n ? queue : new int[0];
}
}
课程表
标准的使用拓扑排序的板子 + 加上链式前向星建图法直接打败 100 %
class Solution {
// 设置点的最大数量
private static final int MAXN = 10001;
// 设置边的最大数量
private static final int MAXM = 10001;
// head数组
private static final int[] head = new int[MAXN];
// next数组
private static final int[] next = new int[MAXM];
// to数组
private static final int[] to = new int[MAXM];
// indegree数组(统计入度)
private static final int[] indegree = new int[MAXN];
// cnt统计边的数量
private static int cnt = 1;
// 添加边的方法(顺便统计入度)
private static void addEdge(int u, int v){
next[cnt] = head[u];
to[cnt] = v;
head[u] = cnt++;
indegree[v]++;
}
// 初始化静态空间(只需要清空head以及indegree数组)然后建图(这里是有向带权图)
private static void build(int n, int[][] edges){
cnt = 1;
for(int i = 0; i <= n; i++){
indegree[i] = 0;
head[i] = 0;
}
for(int[] edge : edges){
addEdge(edge[1], edge[0]);
}
}
// 拓扑排序(topoSort的板子)
private static int[] topoSort(int n){
// 首先创建一个队列(将来可以作为结果返回)
int[] queue = new int[n];
int l = 0;
int r = 0;
// 遍历入度表, 添加所有0入度的点进队列
for(int i = 0; i < n; i++){
if(indegree[i] == 0){
queue[r++] = i;
}
}
// 利用链式前向星的遍历开始跑拓扑排序
int elemCnt = 0;
while(l < r){
int cur = queue[l++];
elemCnt++;
for(int ei = head[cur]; ei != 0; ei = next[ei]){
if(--indegree[to[ei]] == 0){
queue[r++] = to[ei];
}
}
}
return elemCnt == n ? queue : new int[0];
}
public int[] findOrder(int numCourses, int[][] prerequisites) {
build(numCourses, prerequisites);
return topoSort(numCourses);
}
}