图论 经典例题

1 拓扑排序

对有向图的节点排序，使得对于每一条有向边 U-->V U都出现在V之前

*有环无法拓扑排序

indegree[], nxs[];//前者表示节点 i 的入度，后者表示节点 i 指向的节点
queue = []
for i in range(n):if indege[i] == 0: queue.add(i)// 入度为0的节点加入队列
while queue:curnode = queue.popleft()for nx in nxs[curnode]:indegre[nx] -= 1;if indegre[nx] == 0:queue.add(nx);

207 课程表1

#include <vector>
#include <deque>using namespace std;class Solution {
public:bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {// 邻接表vector<vector<int>> nxs(numCourses, vector<int>());// 入度数组vector<int> indegree(numCourses, 0);// 填充入度数组和邻接表for (auto pre : prerequisites) {int a = pre[0];int b = pre[1];// a 的入度增加indegree[a]++;// 将 b 加入 a 的邻接表nxs[b].push_back(a);}deque<int> q;// 1.找到入度为0的点for (int i = 0; i < numCourses; i++) {if (indegree[i] == 0) {q.push_back(i);}}// 2.迭代，更新入度while (!q.empty()) {int curr = q.front();q.pop_front();numCourses--; // 完成一个课程for (int neighbor : nxs[curr]) {if (--indegree[neighbor] == 0) {q.push_back(neighbor);}}}// 如果所有课程都完成了，则返回 truereturn numCourses == 0;}
};

210 课程表II

class Solution {
public:vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {// 邻接表vector<vector<int>> nxs (numCourses, vector<int>());// 入度数组vector<int> indegree (numCourses);// 填充入度数组和邻接表for (auto pre : prerequisites) {int a = pre[0];int b = pre[1];indegree[a]++;nxs[b].push_back(a);}vector<int> res;deque<int> q;int index = 0;for (int i = 0; i < numCourses; ++i) {if (indegree[i] == 0) {q.push_back(i);}}while (!q.empty()) {int k = q.front();q.pop_front();res.push_back(k);index++;for (auto neg : nxs[k]) {if (--indegree[neg] == 0) {q.push_back(neg); }}}if (index != numCourses) {return vector<int>();}else{return res;}    }
};

310 最小高度树

依次删去度数为 1 的点

class Solution {
public:vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {// 找到使得树的高度最小的节点// 找到最中间的点if (n == 1) return vector<int>({0});// 储存度数，而非入度vector<int> degrees(n, 0);// 邻接表vector<vector<int>> adjacencyList(n, vector<int>());for (auto edge : edges) {int a = edge[0];int b = edge[1];degrees[a]++;degrees[b]++;adjacencyList[a].push_back(b);adjacencyList[b].push_back(a);}// 队列，储存入度为 1deque<int> q;// 找到度数为 1 的点for (int i = 0; i < n; ++i) {if (degrees[i] == 1) {q.push_back(i);}}vector<int> res;// 遍历所有边缘节点while (!q.empty()) {res.clear();// 层序更新，这一批点处理完之后，先看结果对不对int len = q.size();for (int i = 0; i < len; ++i) {int node = q.front();q.pop_front();res.push_back(node);// 更新两个矩阵for (auto nex : adjacencyList[node]) {degrees[nex]--;if (degrees[nex] == 1){q.push_back(nex);}}}}return res;}
};

802 逆向拓扑

找到不能进入环的点，跟它在不在环里面没关系

有向图找环

从出度为 0 的点出发，它们不可能在环中

class Solution {
public:vector<int> eventualSafeNodes(vector<vector<int>>& graph) {int n = graph.size();// 出度vector<int> outdegree(n);// 逆向邻接表vector<vector<int>> pre_nodes(n, vector<int>());for (int i = 0; i < n; ++i) {for (auto nx : graph[i]) {// i --> nxoutdegree[i]++;pre_nodes[nx].push_back(i);}}deque<int> q;// 找到出度为 0 的点for (int i = 0; i < n; ++i) {if (outdegree[i] == 0) {q.push_back(i);}}// 储存结果vector<int> res;while (!q.empty()) {int node = q.front();q.pop_front();res.push_back(node);for (auto nex : pre_nodes[node]) {outdegree[nex]--;if (outdegree[nex] == 0) {q.push_back(nex);}}}sort(res.begin(), res.end());return res;}
};

2 并查集

查找连通块的数量

int[] fa;void init(int n) {fa = new int[n];// 初始化for (int i = 0; i < n; ++i) fa[i] = i;// 遍历，都指向自己
}// 0 和 3 是亲戚，则 0 和 3建立链接
int find(int x) {// 如果 x 是自己的 boss 则返回 x// 如果不是，则 return x == fa[x] ? x : (fa[x] = find(fa[x]));// 是否是根节点
}void union(int x, int y) {fa[find(x)] = find(y);// 连通
}

    vector<int> fa; // 并查集的父节点数组// 初始化并查集，设置每个节点的父节点为自己// 0 -- n-1void init(int n) {fa.resize(n);for (int i = 0; i < n; ++i) {fa[i] = i;}}// 查找节点x所在的集合的根节点，同时进行路径压缩int find(int x) {return x == fa[x] ? x : (fa[x] = find(x));}// 合并两个节点所在的集合void uni(int x, int y) {fa[find(x)] = find(y);}

构建并查集的操作基本都是一样的

1.查询根节点 + 路径压缩

2.合并块

题眼一般是多个集合的合并

547 省份数量

并查集 + 求连通块的数量

class Solution {
public:vector<int> fa;// 初始化 n 个城市的父节点为它们自己void init(int n) {fa.resize(n, 0);for (int i = 0; i < n; ++i) {fa[i] = i;}}// 找 x 的夫节点int find(int x) {return x == fa[x] ? x : (fa[x] = find(fa[x]));}// 合并void uni(int x, int y) {fa[find(x)] = find(y);}// 判断多少个根节点int findCircleNum(vector<vector<int>>& isConnected) {int n = isConnected.size();// 初始化init(n);for (int i = 0; i < n; ++i){for (int j = i + 1; j < n; ++j) {if (isConnected[i][j] == 1) uni(i, j);}}// 检查最后有几个点的父节点是它自己，即根的数目int cnt = 0;for (int i = 0; i < n; ++i) {if (fa[i] == i) {cnt++;}}return cnt;}
};

684 冗余连接

根据父节点的特点找冗余路径

class Solution {
public:vector<int> fa;// 节点是 1 -- nvoid init(int n) {fa.resize(n + 1, 0);for (int i = 1; i <= n; ++i) {fa[i] = i;}}int find(int x) {return fa[x] == x ? x : find(fa[x]);}void uni(int x, int y) {fa[find(x)] = find(y);}vector<int> findRedundantConnection(vector<vector<int>>& edges) {int n = edges.size();init(n);for (auto edge : edges) {int a = edge[0];int b = edge[1];// 如果父类节点都一样，那么找到了冗余路径if (find(a) == find(b)) {return edge;} else {uni(a, b);}}return vector<int>();}
};

1319 

先连通，看连通块的数量，连接 n 个块需要 n - 1 个边

class Solution {
public:vector<int> fa;void init(int n) {fa.resize(n);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 uni(int x, int y) {fa[find(x)] = find(y);}int makeConnected(int n, vector<vector<int>>& connections) {// 判断端点是否连通// 如果已经连通可以拆除// 连接 n 个连通块需要 n - 1 个边init(n);int cnt = 0;for (auto con : connections) {int a = con[0];int b = con[1];if (find(a) == find(b)) {cnt++;}else{uni(a, b);}}// 判断连通块的数量int num = 0; // 初始化for (int i = 0; i < n; ++i) {if (fa[i] == i) {num++;}}// 判断边是不是够用if (cnt >= num - 1) {return num - 1;}return -1;}
};

水域大小

变体，需要维护连通块的数量

class Solution {
public:// 需要维护每个连通块的数量vector<int> fa;vector<int> cnts;// 只对根节点生效void init(int n) {fa.resize(n);cnts.resize(n);for (int i = 0; i < n; ++i) {fa[i] = i;cnts[i] = 1;}}int find(int x) {return fa[x] == x ? x : (fa[x] = find(fa[x]));}void uni(int x, int y) {int xp = fa[find(x)], yp = find(y);fa[xp] = yp;cnts[yp] += cnts[xp];}int getId(int x, int y, int col) {return x * col + y;}vector<int> pondSizes(vector<vector<int>>& land) {// x * col + y// 表示八个方向的方向数组vector<vector<int>> dirs = {{0, 1},   // 向右{0, -1},  // 向左{1, 0},   // 向下{-1, 0},  // 向上{1, 1},   // 右下{1, -1},  // 右上{-1, 1},  // 左下{-1, -1}  // 左上};int n = land.size();int m = land[0].size();init(n * m);for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {if (land[i][j] == 0) {for (auto dir : dirs) {// 遍历八个方向int nx = i + dir[0];int ny = j + dir[1];// 如果方向不越界 且 为水域if (nx < 0 || ny < 0 || nx >= n || ny >= m || land[nx][ny] != 0) {continue;}else{int id1 = getId(i, j, m);int id2 = getId(nx, ny, m);if (find(id1) != find(id2)) {uni(id1, id2);}}}}}}vector<int> res;for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {int id = getId(i, j, m);if (fa[id] == id && land[i][j] == 0) {res.push_back(cnts[id]);}}}sort(res.begin(), res.end());return res;}
};

721 账户合并（字符串）

建立映射 [0, a, b] 其中 0 代表人名，a 代表邮箱地址

最后还要倒过来输出

#include <vector>
#include <string>
#include <map>
#include <algorithm>class Solution {
public:// 并查集代码vector<int> fa; // 并查集的父节点数组// 初始化并查集，设置每个节点的父节点为自己void init(int n) {fa.resize(n);for (int i = 0; i < n; ++i) {fa[i] = i;}}// 查找节点x所在的集合的根节点，同时进行路径压缩int find(int x) {return x == fa[x] ? x : find(fa[x]);}// 合并两个节点所在的集合void uni(int x, int y) {fa[find(x)] = find(y);}vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {int n = accounts.size(); // 账号的数量init(n); // 初始化并查集// 邮箱到账号ID的映射map<string, int> email_accId;// 构建并查集，合并具有相同邮箱地址的账号for (int accId = 0; accId < n; accId++) {int m = accounts[accId].size(); // 当前账号的邮箱数量for (int i = 1; i < m; ++i) {string email = accounts[accId][i]; // 获取邮箱地址// 如果邮箱地址不存在，建立映射关系// if (email_accId.find(email) == email_accId.end()) {email_accId[email] = accId; } else {// 当前id和之前id合并uni(accId, email_accId[email]); // 如果邮箱地址已存在，合并账号}}}// 账号ID到邮箱的映射map<int, vector<string>> accId_emails;// 遍历所有邮箱账号，将它们归类到相同的账号ID下for (auto& pair : email_accId) {string email = pair.first;int accId = find(pair.second); // 获取根账号IDaccId_emails[accId].push_back(email);}// 构建最终的合并后的账户列表vector<vector<string>> mergedAccounts;for (auto& pair : accId_emails) {int accId = pair.first;vector<string> emails = pair.second;// 将账号ID添加到前面vector<string> mergedAccount = {accounts[accId][0]};sort(emails.begin(), emails.end()); // 对邮箱地址排序mergedAccount.insert(mergedAccount.end(), emails.begin(), emails.end());mergedAccounts.push_back(mergedAccount);}return mergedAccounts; // 返回合并后的账户列表}
};