leetcode Graph 图论

本次题解包括

• 133 Clone Graph
• 207 Course Schedule
• 210 Course Schedule II
• 547 Number of Provinces
• 684 冗余连接
• 803 打砖块
• 947 移除最多的同行或同列石头
• 1202. Smallest String With Swaps
• 1319. 连通网络的操作次数

133. leetcode Clone Graph

Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

题目地址： leetcode Clone Graph

题意：给定一张图，要求进行深拷贝

思路：leetcode之前唯一的图。。

用BFS/DFS对图进行遍历，我使用字典（c++叫Map)建立起旧结点和新结点的映射关系，这样就好复制啦。

class Solution:
    # @return a undirected graph node
    def cloneGraph(self, node):
        if not node:return None
        head=UndirectedGraphNode(node.label)
        q,vis,dic=[],set([node]),{}
        dic[node]=head
        q.append(node)
        while q:
            cur = q.pop()
            for i in cur.neighbors:
                if i not in dic:
                    dic[i]=UndirectedGraphNode(i.label)
                dic[cur].neighbors.append(dic[i])
                if i not in vis:
                    q.append(i)
                    vis.add(i)
        return head

附上我的测试代码

class UndirectedGraphNode:
    def __init__(self, x):
        self.label = x
        self.neighbors = []

def printGraph(node):
    q ,vis = [],set([node])
    q.append(node)
    while q:
        cur = q.pop(0)
        print '  ',cur.label
        for i in cur.neighbors:
            print i.label
            if i not in vis:
                q.append(i)
                vis.add(i)

s=Solution()
one = UndirectedGraphNode(1)
two = UndirectedGraphNode(2)
three =UndirectedGraphNode(3)
one.neighbors.append(one)
one.neighbors.append(two)
two.neighbors.append(three)
#printGraph(one)
printGraph( s.cloneGraph(one))

 

---

207. leetcode Course Schedule

 There are a total of n courses you have to take, labeled from 0 to n - 1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

For example:

2, [[1,0]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.

2, [[1,0],[0,1]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

题目地址： leetcode Course Schedule

题意：给定一些课程，以及他们课程之间先修的关系。如我要修课程1，必须先修完课程0，问是否有可能完成这些课程。

思路：很明显的问题可以转化为求拓扑排序（Topological Sort）。

拓扑排序的做法如下：

1. 每次找入度为0的点，输出该入度为0的点，并删除与之相连接的边
2. 重复1直到没有入度为0的点。之前输出入度为0的点若小于原图的结点数，那么说明图有环，即拓扑排序不存在，否则即为拓扑排序。

以下面的为例：

Topological Sort

1. 在(a)图中v0和v1的入度都为0，选择v0并输出，接着删去顶点v0及出边<0,2>，得到的结果如(b)图所示。

2. 在(b)图中只有一个入度为0的顶点v1，输出v1，接着删去v1和它的三条出边<1,2>,<1,3>和<1,4>，得到的结果如(c)图所示。

3. 在(c)图中v2和v4的入度都为0，不妨选择v2并输出之，接着删去v2及两条出边<2,3>和<2,5>，得到的结果如(d)图所示。

4. 在(d)图上依次输出顶点v3,v4和v5，并在每个顶点输出后删除该顶点及出边。

C++

class Solution {
public:
	bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
		vector<vector<int> > g(numCourses);
		vector<int> in_degree(numCourses, 0);
		for (int i = 0; i < prerequisites.size(); i++){
			g[prerequisites[i].second].push_back(prerequisites[i].first);
			in_degree[prerequisites[i].first]++;
		}
		queue<int> q;
		for (int i = 0; i < numCourses; i++) if (in_degree[i] == 0) q.push(i);
		while (!q.empty()){
			int cur = q.front();
			q.pop();
			for (auto it = g[cur].begin(); it != g[cur].end(); it++)
				if (--in_degree[*it] == 0) q.push(*it);
		}

		for (int i = 0; i < numCourses; i++) if (in_degree[i] != 0) return false;
		return true;
	}
};

 

---

210. leetcode Course Schedule II

There are a total of n courses you have to take, labeled from 0 to n - 1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.

There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.

For example:

2, [[1,0]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1]

4, [[1,0],[2,0],[3,1],[3,2]]

There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is[0,2,1,3].

题目地址： leetcode Course Schedule II

题意：和207那题一样，给定各种课程之间依赖关系，求一个满足条件的顺序。

思路：其实就是输出拓扑排序啦~直接上面那题代码改改即可。

class Solution {
public:
	vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites)  {
		vector<vector<int> > g(numCourses);
		vector<int> in_degree(numCourses, 0);
		vector<int> ans;
		for (int i = 0; i < prerequisites.size(); i++){
			g[prerequisites[i].second].push_back(prerequisites[i].first);
			in_degree[prerequisites[i].first]++;
		}
		queue<int> q;
		int cnt = 0;
		for (int i = 0; i < numCourses; i++) if (in_degree[i] == 0) q.push(i);
		while (!q.empty()){
			int cur = q.front();
			ans.push_back(cur);
			q.pop();
			for (auto it = g[cur].begin(); it != g[cur].end(); it++)
				if (--in_degree[*it] == 0) q.push(*it);
		}

		if (ans.size() == numCourses) return ans;
		ans.clear();
		return ans;
	}
};

547. 省份数量

有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。

省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。

给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。

返回矩阵中 省份 的数量。

示例 1：

img

>输入：isConnected = [[1,1,0],[1,1,0],[0,0,1]]
>输出：2

示例 2：

img

>输入：isConnected = [[1,0,0],[0,1,0],[0,0,1]]
>输出：3

提示：

• 1 <= n <= 200
• n == isConnected.length
• n == isConnected[i].length
• isConnected[i][j] 为 1 或 0
• isConnected[i][i] == 1
• isConnected[i][j] == isConnected[j][i]

方法1：dfs即可

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        vis = [False] * len(isConnected)
        ans = 0
        for i in range(len(isConnected)):
            if vis[i]:
                continue
            ans += 1
            vis[i] = True
            self.dfs(i, isConnected, vis)
        return ans
    
    def dfs(self, cur, isConnected, vis):
        row = isConnected[cur]
        for i in range(len(row)):
            if row[i] and not vis[i]:
                vis[cur] = True
                self.dfs(i, isConnected, vis)

方法2： 并查集

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        fa = list(range(len(isConnected)))
        for i in range(len(isConnected)):
            for j in range(i):
                if isConnected[i][j]:
                    root_x = self.find(i, fa)
                    root_y = self.find(j, fa)
                    if root_x != root_y:
                        fa[root_y] = root_x

        return sum([1 if i == fa[i] else 0 for i in range(len(isConnected))])
    
    def find(self, cur, fa):
        if fa[cur] == cur: return cur
        fa[cur] = self.find(fa[cur], fa)
        return fa[cur]

684. 冗余连接

在本问题中, 树指的是一个连通且无环的无向图。

输入一个图，该图由一个有着N个节点 (节点值不重复1, 2, ..., N) 的树及一条附加的边构成。附加的边的两个顶点包含在1到N中间，这条附加的边不属于树中已存在的边。

结果图是一个以边组成的二维数组。每一个边的元素是一对[u, v] ，满足 u < v，表示连接顶点u 和v的无向图的边。

返回一条可以删去的边，使得结果图是一个有着N个节点的树。如果有多个答案，则返回二维数组中最后出现的边。答案边 [u, v] 应满足相同的格式 u < v。

示例 1：

>输入: [[1,2], [1,3], [2,3]]
>输出: [2,3]
>解释: 给定的无向图为:
 1
/ \
>2 - 3

示例 2：

>输入: [[1,2], [2,3], [3,4], [1,4], [1,5]]
>输出: [1,4]
>解释: 给定的无向图为:
>5 - 1 - 2
   |   |
   4 - 3

注意:

• 输入的二维数组大小在 3 到 1000。
• 二维数组中的整数在1到N之间，其中N是输入数组的大小。

更新(2017-09-26): 我们已经重新检查了问题描述及测试用例，明确图是无向 图。对于有向图详见冗余连接II。对于造成任何不便，我们深感歉意。

低配版本的kruskal算法（不像MST要排序），并查集即可

class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        max_n = 0
        for edge in edges:
            max_n = max(max_n, edge[1])
        
        fa = [i for i in range(max_n + 1)]
        for edge in edges:
            x, y = edge
            root_x = self.find(x, fa)
            root_y = self.find(y, fa)
            if root_x != root_y:
                fa[root_y] = root_x
            else:
                return edge
        return []
    
    def find(self, x, fa):
        if x != fa[x]:
            fa[x] = self.find(fa[x], fa)
        return fa[x]

778. 水位上升的泳池中游泳

在一个 N x N 的坐标方格 grid 中，每一个方格的值 grid[i][j] 表示在位置 (i,j) 的平台高度。

现在开始下雨了。当时间为 t 时，此时雨水导致水池中任意位置的水位为 t 。你可以从一个平台游向四周相邻的任意一个平台，但是前提是此时水位必须同时淹没这两个平台。假定你可以瞬间移动无限距离，也就是默认在方格内部游动是不耗时的。当然，在你游泳的时候你必须待在坐标方格里面。

你从坐标方格的左上平台 (0，0) 出发。最少耗时多久你才能到达坐标方格的右下平台 (N-1, N-1)？

示例 1:

>输入: [[0,2],[1,3]]
>输出: 3
>解释:
>时间为0时，你位于坐标方格的位置为 (0, 0)。
>此时你不能游向任意方向，因为四个相邻方向平台的高度都大于当前时间为 0 时的水位。

>等时间到达 3 时，你才可以游向平台 (1, 1). 因为此时的水位是 3，坐标方格中的平台没有比水位 3 更高的，所以你可以游向坐标方格中的任意位置

示例2:

>输入: [[0,1,2,3,4],[24,23,22,21,5],[12,13,14,15,16],[11,17,18,19,20],[10,9,8,7,6]]
>输出: 16
>解释:
0  1  2  3  4
>24 23 22 21  5
>12 13 14 15 16
>11 17 18 19 20
>10  9  8  7  6

>最终的路线用加粗进行了标记。
>我们必须等到时间为 16，此时才能保证平台 (0, 0) 和 (4, 4) 是连通的

提示:

1. 2 <= N <= 50.
2. grid[i][j] 是 [0, ..., N*N - 1] 的排列。

方法1 最短路

用dijkstra算法，能到达点b的权值为max(weight_b, cur.weight) ，一个是路上累计的最大，一个是当前b点的权值。

struct Node {
    int x;
    int y;
    int t;
    Node(int i, int j, int t) : x(i), y(j), t(t) {}
    bool operator< (const Node& o) const {
        return t > o.t;
    }
};

class Solution {
public:
    int swimInWater(vector<vector<int>>& grid) {
        priority_queue<Node> q;
        const int n = grid.size();
        vector<vector<bool>> vis(n, vector<bool>(n, false));
        q.push(Node(0, 0, grid[0][0]));
        int dx[] = {1, -1, 0, 0};
        int dy[] = {0, 0, 1, -1};
        while (!q.empty()) {
            Node cur = q.top();
            q.pop();
            if (cur.x == n - 1 && cur.y == n - 1) {
                return cur.t;
            }
            if (vis[cur.x][cur.y]) continue;
            vis[cur.x][cur.y] = true;
            for (int i = 0; i < 4; ++i) {
                int nx = cur.x + dx[i];
                int ny = cur.y + dy[i];
                if (nx < 0 || ny < 0 || nx == n || ny == n || vis[nx][ny]) {
                    continue;
                }
                q.push(Node(nx, ny, max(grid[nx][ny], cur.t)));
            }
        }
        return -1;
    }
};

方法2 并查集

将权值从小到大排序（由于本题为0～n*n-1，可以用类似计数排序），然后遍历权值，若当前权值大于四周的点，则可以合并两个连通分支，因为在当前的时刻t，可以到当前的点必然也能到相邻的点。若加入某个点后起点和终点连通，则找到了解

class UnionFind {
public:
    UnionFind(int n) {
        _fa.resize(n, 0);
        for (int i = 0; i < n; ++i) {
            _fa[i] = i;
        }
    }

    int find(int x) {
        return _fa[x] == x ? x : _fa[x] = find(_fa[x]);
    }

    void union_fa(int x, int y) {
        int root_x = find(x);
        int root_y = find(y);
        if (root_x != root_y) {
            _fa[root_x] = root_y;
        }
    }

private:
    vector<int> _fa;
};

class Solution {
public:
    int swimInWater(vector<vector<int>>& grid) {
        const int n = grid.size();
        UnionFind uf(n * n);
        vector<pair<int, int>> idx(n * n);
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                idx[grid[i][j]] = std::make_pair(i, j);
            }
        }
        
        const int max_t = n * n - 1;
        vector<int> dx = {0, 0, 1, -1};
        vector<int> dy = {1, -1, 0, 0};
        for (int cur_t = 0; cur_t <= max_t; ++cur_t) {
            auto [x, y] = idx[cur_t];
            for (int i = 0; i < 4; ++i) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (nx < 0 || ny < 0 || nx == n || ny == n || grid[nx][ny] > cur_t) {
                    continue;
                }
                uf.union_fa(x * n + y, nx * n + ny);
            }

            if (uf.find(0) == uf.find(n * n - 1)) {
                return cur_t;
            }
        }
        return -1;
    }
};

方法3 类似1631二分搜索

803. 打砖块

有一个 m x n 的二元网格，其中 1 表示砖块，0 表示空白。砖块 稳定（不会掉落）的前提是：

• 一块砖直接连接到网格的顶部，或者
• 至少有一块相邻（4 个方向之一）砖块 稳定 不会掉落时

给你一个数组 hits ，这是需要依次消除砖块的位置。每当消除 hits[i] = (rowi, coli) 位置上的砖块时，对应位置的砖块（若存在）会消失，然后其他的砖块可能因为这一消除操作而掉落。一旦砖块掉落，它会立即从网格中消失（即，它不会落在其他稳定的砖块上）。

返回一个数组 result ，其中 result[i] 表示第 i 次消除操作对应掉落的砖块数目。

注意，消除可能指向是没有砖块的空白位置，如果发生这种情况，则没有砖块掉落。

示例 1：

>输入：grid = [[1,0,0,0],[1,1,1,0]], hits = [[1,0]]
>输出：[2]
>解释：
>网格开始为：
>[[1,0,0,0]，
[1,1,1,0]]
>消除 (1,0) 处加粗的砖块，得到网格：
>[[1,0,0,0]
[0,1,1,0]]
>两个加粗的砖不再稳定，因为它们不再与顶部相连，也不再与另一个稳定的砖相邻，因此它们将掉落。得到网格：
>[[1,0,0,0],
[0,0,0,0]]
>因此，结果为 [2] 。

示例 2：

>输入：grid = [[1,0,0,0],[1,1,0,0]], hits = [[1,1],[1,0]]
>输出：[0,0]
>解释：
>网格开始为：
>[[1,0,0,0],
[1,1,0,0]]
>消除 (1,1) 处加粗的砖块，得到网格：
>[[1,0,0,0],
[1,0,0,0]]
>剩下的砖都很稳定，所以不会掉落。网格保持不变：
>[[1,0,0,0], 
[1,0,0,0]]
>接下来消除 (1,0) 处加粗的砖块，得到网格：
>[[1,0,0,0],
[0,0,0,0]]
>剩下的砖块仍然是稳定的，所以不会有砖块掉落。
>因此，结果为 [0,0] 。

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 200
• grid[i][j] 为 0 或 1
• 1 <= hits.length <= 4 * 104
• hits[i].length == 2
• 0 <= xi <= m - 1
• 0 <= yi <= n - 1
• 所有 (xi, yi) 互不相同

并查集+逆向思维法。

首先，一块砖是稳定的仅当与屋顶连接，或者周围4个方块有一个是稳定的。当我们消除一个砖块的时候，可能会破坏这个稳定的结构，导致一堆砖块掉落。

注意到一块砖是稳定的=>说明它直接或间接的和屋顶连接=》其他和该砖头连接的都可以看成是一个稳定的连通子图。因此感觉可以用并查集来做。但是并查集是相当于是对两个连通子图的合并，而这道题消除砖块变成连通分量的分解，因此可以考虑逆向思维。

1. 消除所有hits的砖块，即将grid中在hits数组对应的位置上都设置为0
2. 可以首先将与屋顶连接的砖块看成同一个连通分量，因为和任意一个连接都没有什么区别。因此用并查集将他们合并
3. 初始化其他的砖块，将数值为1的合并起来
4. 经过2和3，就形成了若干个连通分量
5. 逆序遍历hits数组，对位置x ,y ：
   1. 首先确保这个位置原先是1，否则相当于hit了空的位置，这里不该补上1
   2. 如果x == 0说明这个砖块是和屋顶直接连接的，要先和屋顶合并一下（否则可能这个砖头连接的其他的砖头都不和屋顶连接了）
   3. 合并x, y周围的联通分量
   4. 设pre_num为合并前屋顶联通分量的儿子的数目，after_num为合并后的数量，则通过补上x,y 连接了after_num - pre_num - 1的数量

代码如下：

class Solution:
    dx = [0, 0, -1, 1]
    dy = [1, -1, 0, 0]

    def hitBricks(self, grid: List[List[int]], hits: List[List[int]]) -> List[int]:
        origin_grid = copy.deepcopy(grid)
        for x, y in hits:
            grid[x][y] = 0
        
        self.m, self.n = len(grid), len(grid[0])
        roof_key = self.get_key(self.m, self.n) # 屋顶的key
        unionfind = UnionFind(roof_key + 1)
        for j in range(self.n):
            if grid[0][j] == 1:
                unionfind.union(self.get_key(0, j), roof_key)

        for i in range(1, self.m):
            for j in range(self.n):
                if grid[i][j] == 0:
                    continue

                if grid[i - 1][j]:
                    unionfind.union(self.get_key(i, j), self.get_key(i - 1, j))
                if j and grid[i][j - 1]:
                    unionfind.union(self.get_key(i, j), self.get_key(i, j - 1))

        ans = []
        for x, y in hits[::-1]:
            if origin_grid[x][y] == 0:
                ans.append(0)
                continue

            cur_key = self.get_key(x, y)
            pre_num = unionfind.get_count(roof_key)
            if x == 0:
                unionfind.union(cur_key, roof_key)
            for i in range(4):
                nx, ny = x + self.dx[i], y + self.dy[i]
                if nx < 0 or ny < 0 or nx >= len(grid) or ny >= len(grid[0]) or \
                        not grid[nx][ny]:
                    continue
                unionfind.union(cur_key, self.get_key(nx, ny))
            
            after_num = unionfind.get_count(roof_key)
            cur = max(after_num - pre_num - 1, 0)
            ans.append(cur)
            grid[x][y] = 1
        return ans[::-1]

    def get_key(self, x, y):
        return x * self.n + y

class UnionFind(object):
    def __init__(self, n):
        self.fa = [i for i in range(n)]
        self.counter = [1] * n
    
    def find(self, x):
        if x != self.fa[x]:
            self.fa[x] = self.find(self.fa[x])
        return self.fa[x]

    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x == root_y:
            return
        self.fa[root_y] = root_x
        self.counter[root_x] += self.counter[root_y]

    def get_count(self, x):
        root_x = self.find(x)
        return self.counter[root_x]

947. 移除最多的同行或同列石头

n 块石头放置在二维平面中的一些整数坐标点上。每个坐标点上最多只能有一块石头。

如果一块石头的 同行或者同列 上有其他石头存在，那么就可以移除这块石头。

给你一个长度为 n 的数组 stones ，其中 stones[i] = [xi, yi] 表示第 i 块石头的位置，返回 可以移除的石子 的最大数量。

示例 1：

>输入：stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
>输出：5
>解释：一种移除 5 块石头的方法如下所示：
>1. 移除石头 [2,2] ，因为它和 [2,1] 同行。
>2. 移除石头 [2,1] ，因为它和 [0,1] 同列。
>3. 移除石头 [1,2] ，因为它和 [1,0] 同行。
>4. 移除石头 [1,0] ，因为它和 [0,0] 同列。
>5. 移除石头 [0,1] ，因为它和 [0,0] 同行。
>石头 [0,0] 不能移除，因为它没有与另一块石头同行/列。

示例 2：

>输入：stones = [[0,0],[0,2],[1,1],[2,0],[2,2]]
>输出：3
>解释：一种移除 3 块石头的方法如下所示：
>1. 移除石头 [2,2] ，因为它和 [2,0] 同行。
>2. 移除石头 [2,0] ，因为它和 [0,0] 同列。
>3. 移除石头 [0,2] ，因为它和 [0,0] 同行。
>石头 [0,0] 和 [1,1] 不能移除，因为它们没有与另一块石头同行/列。

示例 3：

>输入：stones = [[0,0]]
>输出：0
>解释：[0,0] 是平面上唯一一块石头，所以不可以移除它。

提示：

• 1 <= stones.length <= 1000
• 0 <= xi, yi <= 10^4
• 不会有两块石头放在同一个坐标点上

题目说，如果一块石头的 同行或者同列 上有其他石头存在，那么就可以移除这块石头。

容易想到，可以根据这个规则将同行或者同列的删除得剩下一个石头。比如下面的，由于同行同列可以删除，最优的做法就是删除得剩下一个。

1 0 0 1
0 1 0 0
0 1 0 1

这就又是并查集的思路了：每个连通子图都可以剩下一个，那么答案就是总共的石头数目-连通子图的个数。

所以对于x, y坐标就是把横纵坐标合并为一个子图。由于x, y < 10^4，因此可以将y的坐标加上10001来区分x, y坐标。

class Solution:
    def removeStones(self, stones: List[List[int]]) -> int:
        fa = {}
        for (x, y) in stones:
            root_x = self.find(fa, x)
            root_y = self.find(fa, y + 10001)
            if root_x != root_y:
                fa[root_y] = root_x

        cnt = 0
        for x, root_x in fa.items():
            if x == root_x:
                cnt += 1
        return len(stones) - cnt

    def find(self, fa, x):
        if x not in fa:
            fa[x] = x
            return x
        if x == fa[x]:
            return fa[x]
        fa[x] = self.find(fa, fa[x])
        return fa[x]

959. 由斜杠划分区域

在由 1 x 1 方格组成的 N x N 网格 grid 中，每个 1 x 1 方块由 /、\ 或空格构成。这些字符会将方块划分为一些共边的区域。

（请注意，反斜杠字符是转义的，因此 \ 用 "\\" 表示。）。

返回区域的数目。

示例 1：

>输入：
>[
 " /",
 "/ "
>]
>输出：2
>解释：2x2 网格如下：

示例 2：

>输入：
>[
 " /",
 "  "
>]
>输出：1
>解释：2x2 网格如下：

示例 3：

>输入：
>[
 "\\/",
 "/\\"
>]
>输出：4
>解释：（回想一下，因为 \ 字符是转义的，所以 "\\/" 表示 \/，而 "/\\" 表示 /\。）
>2x2 网格如下：

示例 4：

>输入：
>[
 "/\\",
 "\\/"
>]
>输出：5
>解释：（回想一下，因为 \ 字符是转义的，所以 "/\\" 表示 /\，而 "\\/" 表示 \/。）
>2x2 网格如下：

示例 5：

>输入：
>[
 "//",
 "/ "
>]
>输出：3
>解释：2x2 网格如下：

提示：

1. 1 <= grid.length == grid[0].length <= 30
2. grid[i][j] 是 '/'、'\'、或 ' '。

这题很容易想到并查集，但是难的是建图，可以把一个位置分成如下四个小区域，若当前字符为：

• 空格：则合并4个区域
• /： 合并03, 12
• \: 合并 01, 23

image.png

图片来自https://leetcode-cn.com/problems/regions-cut-by-slashes/solution/you-xie-gang-hua-fen-qu-yu-by-leetcode-67xb/

那么不同块直接处理呢？注意到当前位置的“1”和右边的“3”肯定是能连接的，不管是什么符号。而当前位置的“2”和下面的"0"也是一定能连接的，因此直接合并即可。

class Solution:
    def regionsBySlashes(self, grid: List[str]) -> int:
        n = len(grid)
        uf = UnionFind(4 * n * n)
        for i in range(n):
            for j in range(n):
                c = grid[i][j]
                start = self.pos(i, j, n)
                if c == ' ':
                    uf.union(start, start + 1)
                    uf.union(start, start + 2)
                    uf.union(start, start + 3)
                elif c == '/':
                    uf.union(start, start + 3)
                    uf.union(start + 1, start + 2)
                else: #\
                    uf.union(start, start + 1)
                    uf.union(start + 2, start + 3)

                if j + 1 < n:
                    right_start = self.pos(i, j + 1, n)
                    uf.union(start + 1, right_start + 3)
                if i + 1 < n:
                    down_start = self.pos(i + 1, j, n)
                    uf.union(start + 2, down_start)
        
        return uf.get_root_count()
    
    def pos(self, i, j, n):
        return i * 4 * n + j * 4

class UnionFind:
    def __init__(self, n):
        self.fa = [i for i in range(n)]
        self.count = n

    def get_root_count(self,):
        return self.count

    def find(self, x):
        if x != self.fa[x]:
            self.fa[x] = self.find(self.fa[x])
        return self.fa[x]
    
    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x != root_y:
            self.fa[root_y] = root_x
            self.count -= 1

1202. 交换字符串中的元素

给你一个字符串 s，以及该字符串中的一些「索引对」数组 pairs，其中 pairs[i] = [a, b] 表示字符串中的两个索引（编号从 0 开始）。

你可以 任意多次交换 在 pairs 中任意一对索引处的字符。

返回在经过若干次交换后，s 可以变成的按字典序最小的字符串。

示例 1:

>输入：s = "dcab", pairs = [[0,3],[1,2]]
>输出："bacd"
>解释： 
>交换 s[0] 和 s[3], s = "bcad"
>交换 s[1] 和 s[2], s = "bacd"

示例 2：

>输入：s = "dcab", pairs = [[0,3],[1,2],[0,2]]
>输出："abcd"
>解释：
>交换 s[0] 和 s[3], s = "bcad"
>交换 s[0] 和 s[2], s = "acbd"
>交换 s[1] 和 s[2], s = "abcd"

示例 3：

>输入：s = "cba", pairs = [[0,1],[1,2]]
>输出："abc"
>解释：
>交换 s[0] 和 s[1], s = "bca"
>交换 s[1] 和 s[2], s = "bac"
>交换 s[0] 和 s[1], s = "abc"

提示：

• 1 <= s.length <= 10^5
• 0 <= pairs.length <= 10^5
• 0 <= pairs[i][0], pairs[i][1] < s.length
• s 中只含有小写英文字母

这题有一个pairs数组，可以任意多次交换，容易想到的是，[0, 3]能交换，[3, 6]能交换，那么[0, 6]也能交换（具有传递性）。

因此可以用一个并查集，来找到所有的连通分量，对于同一组连通分量的，进行排序，然后按大小输出即可。

注意这里由于只有小写字母，因此可以用计数排序。

class Solution {
public:
    string smallestStringWithSwaps(string s, vector<vector<int>>& pairs) {
        vector<int> fa(s.size(), 0);
        for (std::size_t i = 0; i < s.size(); ++i) {
            fa[i] = i;
        }

        for (auto& pair : pairs) {
            int root_x = find(pair[0], fa);
            int root_y = find(pair[1], fa);
            fa[root_y] = root_x;
        }

        unordered_map<int, vector<int>> counter;
        for (std::size_t i = 0; i < s.size(); ++i) {
            int root = find(i, fa);
            if (counter.find(root) == counter.end()) {
                counter[root] = vector(26, 0);
            }
            ++counter[root][s[i] - 'a'];
        }

        stringstream ss;
        for (std::size_t i = 0; i < s.size(); ++i) {
            int root = find(i, fa);
            vector<int>& cnt = counter[root];
            for (std::size_t j = 0; j < 26; ++j) {
                if (cnt[j] > 0) {
                    --cnt[j];
                    ss << char('a' + j);
                    break;
                }
            }
        }
        return ss.str();
    }

    int find(int cur, vector<int>& fa) {
        return cur == fa[cur]? cur : fa[cur] = find(fa[cur], fa);
    }
};

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]
• 没有重复的连接。
• 两台计算机不会通过多条线缆连接。

将两个线断开，然后去连接没有连接的计算机，相当于连接两个连通分量。因为断开的线必然是不影响原来连通分量的连通性的，否则就不能断开。

因此可以用并查集，首先将所有节点合并，看有几个连通分量，只需要将多余的线断开并连接即可。因此答案为连通分量数 - 1

注意无解的情况就是本身的线少于n - 1条的情况。

class Solution:
    def makeConnected(self, n: int, connections: List[List[int]]) -> int:
        if len(connections) < n - 1: return -1
        uf = UnionFind(n)
        for a, b in connections:
            uf.union(a, b)
        root_nodes = uf.get_root_nodes()
        return len(root_nodes) - 1

class UnionFind:
    def __init__(self, n):
        self.fa = [i for i in range(n)]

    def get_root_nodes(self,):
        return [i for i in range(len(self.fa)) if i == self.fa[i]] 

    def find(self, x):
        if x != self.fa[x]:
            self.fa[x] = self.find(self.fa[x])
        return self.fa[x]
    
    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x != root_y:
            self.fa[root_y] = root_x

1489. 找到最小生成树里的关键边和伪关键边

给你一个 n 个点的带权无向连通图，节点编号为 0 到 n-1 ，同时还有一个数组 edges ，其中 edges[i] = [from``i, toi, weighti] 表示在 fromi 和 toi 节点之间有一条带权无向边。最小生成树 (MST) 是给定图中边的一个子集，它连接了所有节点且没有环，而且这些边的权值和最小。

请你找到给定图中最小生成树的所有关键边和伪关键边。如果从图中删去某条边，会导致最小生成树的权值和增加，那么我们就说它是一条关键边。伪关键边则是可能会出现在某些最小生成树中但不会出现在所有最小生成树中的边。

请注意，你可以分别以任意顺序返回关键边的下标和伪关键边的下标。

示例 1：

img

>输入：n = 5, edges = [[0,1,1],[1,2,1],[2,3,2],[0,3,2],[0,4,3],[3,4,3],[1,4,6]]
>输出：[[0,1],[2,3,4,5]]
>解释：上图描述了给定图。
>下图是所有的最小生成树。

>注意到第 0 条边和第 1 条边出现在了所有最小生成树中，所以它们是关键边，我们将这两个下标作为输出的第一个列表。
>边 2，3，4 和 5 是所有 MST 的剩余边，所以它们是伪关键边。我们将它们作为输出的第二个列表。

示例 2 ：

img

>输入：n = 4, edges = [[0,1,1],[1,2,1],[2,3,1],[0,3,1]]
>输出：[[],[0,1,2,3]]
>解释：可以观察到 4 条边都有相同的权值，任选它们中的 3 条可以形成一棵 MST 。所以 4 条边都是伪关键边。

提示：

• 2 <= n <= 100
• 1 <= edges.length <= min(200, n * (n - 1) / 2)
• edges[i].length == 3
• 0 <= fromi < toi < n
• 1 <= weighti <= 1000
• 所有 (fromi, toi) 数对都是互不相同的。

首先用kruskal算法生成最小生成树，然后枚举MST的每一条边mst_i：

• 初始化一个新的并查集，将除了mst_i外的所有边都合并
• 遍历edges，若能找不到边能生成MST或者两个连通分量的权值会增加，则说明是关键边，否则为伪关建边

注意由于一开始将数组排序的，所以最后还要将排好序的数组和一开始的数组下标对应

class Solution:
    def findCriticalAndPseudoCriticalEdges(self, n: int, edges: List[List[int]]) -> List[List[int]]:
        edges = [(i, x, y, w) for i, (x, y, w) in enumerate(edges)]
        edges.sort(key=lambda x: x[-1])
        uf = UnionFind(n)
        mst_edge_index = []
        mst_weight = 0
        for i, (_, x, y, w) in enumerate(edges):
            root_x = uf.find(x)
            root_y = uf.find(y)
            if root_x != root_y:
                mst_weight += w
                mst_edge_index.append(i)
                uf.union(root_x, root_y)
                if len(mst_edge_index) >= n - 1:
                    break
        key_list = []
        fake_key_list = []
        if len(mst_edge_index) != n - 1:
            return [key_list, fake_key_list]
        
        for mst_i in mst_edge_index:
            temp_uf = UnionFind(n)
            temp_w = 0
            for i in mst_edge_index:
                if mst_i == i:
                    continue
                _, x, y, w = edges[i]
                temp_uf.union(x, y)
                temp_w += w
            
            find_equal = False
            find_two_graph_edge = False
            for i in range(mst_i + 1, len(edges)): # 从mst_i + 1 开始
                _, x, y, w = edges[i]
                root_x = temp_uf.find(x)
                root_y = temp_uf.find(y)
                if root_x == root_y:
                    continue
                
                find_two_graph_edge = True
                if temp_w + w == mst_weight:
                    find_equal = True
                    fake_key_list.append(i)
                elif temp_w + w > mst_weight:
                    break
            
            if not find_two_graph_edge or not find_equal:
                key_list.append(mst_i)
            else:
                fake_key_list.append(mst_i)

        key_list = [edges[i][0] for i in key_list]
        fake_key_list = [edges[i][0] for i in set(fake_key_list)]
        return [key_list, fake_key_list]

class UnionFind:
    def __init__(self, n):
        self.fa = [i for i in range(n)]

    def find(self, x):
        if x != self.fa[x]:
            self.fa[x] = self.find(self.fa[x])
        return self.fa[x]
    
    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x != root_y:
            self.fa[root_y] = root_x

1631. 最小体力消耗路径

你准备参加一场远足活动。给你一个二维 rows x columns 的地图 heights ，其中 heights[row][col] 表示格子 (row, col) 的高度。一开始你在最左上角的格子 (0, 0) ，且你希望去最右下角的格子 (rows-1, columns-1) （注意下标从 0 开始编号）。你每次可以往 上，下，左，右 四个方向之一移动，你想要找到耗费 体力 最小的一条路径。

一条路径耗费的 体力值 是路径上相邻格子之间 高度差绝对值 的 最大值 决定的。

请你返回从左上角走到右下角的最小 体力消耗值 。

示例 1：

img

>输入：heights = [[1,2,2],[3,8,2],[5,3,5]]
>输出：2
>解释：路径 [1,3,5,3,5] 连续格子的差值绝对值最大为 2 。
>这条路径比路径 [1,2,2,2,5] 更优，因为另一条路径差值最大值为 3 。

示例 2：

img

>输入：heights = [[1,2,3],[3,8,4],[5,3,5]]
>输出：1
>解释：路径 [1,2,3,4,5] 的相邻格子差值绝对值最大为 1 ，比路径 [1,3,5,3,5] 更优。

示例 3：

img

>输入：heights = [[1,2,1,1,1],[1,2,1,2,1],[1,2,1,2,1],[1,2,1,2,1],[1,1,1,2,1]]
>输出：0
>解释：上图所示路径不需要消耗任何体力。

提示：

• rows == heights.length
• columns == heights[i].length
• 1 <= rows, columns <= 100
• 1 <= heights[i][j] <= 106

方法1. 最短路径

用最短路径的算法如dijkstra

struct Node {
    int x;
    int y;
    int cost;
    Node(int x, int y, int cost) : x(x), y(y), cost(cost) {}
    bool operator < (const Node& o) const {
        return cost > o.cost;
    }
};

class Solution {
public:
    int minimumEffortPath(vector<vector<int>>& heights) {
        if (heights.empty()) return 0;
        const int m = heights.size();
        const int n = heights[0].size();
        vector<vector<bool>> vis(m, vector<bool>(n, false));
        vector<vector<int>> dis(m, vector<int>(n, INT_MAX));
        priority_queue<Node> q;
        q.push(Node(0, 0, 0));
        int dx[] = {1, -1, 0, 0};
        int dy[] = {0, 0, 1, -1};
        while (!q.empty()) {
            Node cur = q.top();
            q.pop();
            if (vis[cur.x][cur.y]) {
                continue;
            }
            if (cur.x == m - 1 && cur.y == n - 1) {
                return cur.cost;
            }
            vis[cur.x][cur.y] = true;
            for (int i = 0; i < 4; ++i) {
                int nx = cur.x + dx[i];
                int ny = cur.y + dy[i];
                if (nx < 0 || ny < 0 || nx >= m || ny >= n || vis[nx][ny]) {
                    continue;
                }
                int temp = abs(heights[nx][ny] - heights[cur.x][cur.y]);
                temp = max(temp, cur.cost);
                if (temp < dis[nx][ny]) {
                    dis[nx][ny] = temp;
                    q.push(Node(nx, ny, temp));
                }
            }
        }
        return -1;
    }
};

方法2.二分搜索

设答案为mid，然后遍历图，每次只能遍历权重差不大于mid的点。

如果能到达右下角，则设right = mid缩小范围，否则left = mid + 1增大权重

class Solution {
public:
    int minimumEffortPath(vector<vector<int>>& heights) {
        if (heights.empty()) return 0;
        const int m = heights.size();
        const int n = heights[0].size();
        
        int dx[] = {1, -1, 0, 0};
        int dy[] = {0, 0, 1, -1};
        int left = 0, right = 1e6 + 1;
        while (left < right) {
            int mid = left + ((right - left) >> 1);
            queue<pair<int, int>> q;
            vector<vector<bool>> vis(m, vector<bool>(n, false));
            q.emplace(0, 0);
            vis[0][0] = true;
            while (!q.empty()) {
                auto [x, y] = q.front();
                q.pop();
                if (x == m - 1 && y == n - 1) {
                    break;
                }
                for (int i = 0; i < 4; ++i) {
                    int nx = x + dx[i];
                    int ny = y + dy[i];
                    if (nx < 0 || ny < 0 || nx >= m || ny >= n || vis[nx][ny]) {
                        continue;
                    }
                    if (abs(heights[nx][ny] - heights[x][y]) <= mid) {
                        q.emplace(nx, ny);
                        vis[nx][ny] = true;
                    }
                }
            }

            if (vis[m - 1][n - 1]) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
};

方法3. 并查集

将一个点和它右边、下方两个点边的权值（就是相减的绝对值）放入列表中，按权值从小到大排序。

从小到大遍历边，用并查集合并两个点，若合并后起点和终点连通，则说明找到了答案。PS：需要注意只有一个点的情况， 返回0。

class UnionFind {
public:
    UnionFind(int n) {
        _fa.resize(n);
        for (int i = 0; i < n; ++i) {
            _fa[i] = i;
        }
    }

    int find(int x) {
        return x == _fa[x] ? x : _fa[x] = find(_fa[x]);
    }

    void union_fa(int x, int y) {
        int root_x = find(x);
        int root_y = find(y);
        if (root_x != root_y) {
            _fa[root_y] = root_x;
        }
    }
private:
    vector<int> _fa;
};

class Solution {
public:
    int minimumEffortPath(vector<vector<int>>& heights) {
        if (heights.empty()) return 0;
        const int m = heights.size();
        const int n = heights[0].size();
        
        vector<tuple<int, int, int>> values;
        values.reserve(m * n);
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (i + 1 != m) {
                    values.emplace_back(abs(heights[i][j] - heights[i + 1][j]), i * n + j, (i + 1) * n + j);
                }
                if (j + 1 != n) {
                    values.emplace_back(abs(heights[i][j] - heights[i][j + 1]), i * n + j, i * n + j + 1);
                }
            }
        }
        sort(values.begin(), values.end());
        UnionFind uf(m * n);
        for (auto [w, key1, key2] : values) {
            uf.union_fa(key1, key2);
            if (uf.find(0) == uf.find(m * n - 1)) {
                return w;
            }
        }
        return 0;
    }
};