网站建设与管理实训总结,网上做网站赚钱吗,动态图表网站,公司注册资金查询1 拓扑排序
对有向图的节点排序#xff0c;使得对于每一条有向边 U--V U都出现在V之前
*有环无法拓扑排序
indegree[], nxs[];//前者表示节点 i 的入度#xff0c;后者表示节点 i 指向的节点
queue []
for i in range(n):if indege[i] 0: queue.add(i)// 入度为0的节…
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 dequeusing namespace std;class Solution {
public:bool canFinish(int numCourses, vectorvectorint prerequisites) {// 邻接表vectorvectorint nxs(numCourses, vectorint());// 入度数组vectorint 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);}dequeint 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:vectorint findOrder(int numCourses, vectorvectorint prerequisites) {// 邻接表vectorvectorint nxs (numCourses, vectorint());// 入度数组vectorint indegree (numCourses);// 填充入度数组和邻接表for (auto pre : prerequisites) {int a pre[0];int b pre[1];indegree[a];nxs[b].push_back(a);}vectorint res;dequeint 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 vectorint();}else{return res;} }
};
310 最小高度树
依次删去度数为 1 的点 class Solution {
public:vectorint findMinHeightTrees(int n, vectorvectorint edges) {// 找到使得树的高度最小的节点// 找到最中间的点if (n 1) return vectorint({0});// 储存度数而非入度vectorint degrees(n, 0);// 邻接表vectorvectorint adjacencyList(n, vectorint());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);}// 队列储存入度为 1dequeint q;// 找到度数为 1 的点for (int i 0; i n; i) {if (degrees[i] 1) {q.push_back(i);}}vectorint 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:vectorint eventualSafeNodes(vectorvectorint graph) {int n graph.size();// 出度vectorint outdegree(n);// 逆向邻接表vectorvectorint pre_nodes(n, vectorint());for (int i 0; i n; i) {for (auto nx : graph[i]) {// i -- nxoutdegree[i];pre_nodes[nx].push_back(i);}}dequeint q;// 找到出度为 0 的点for (int i 0; i n; i) {if (outdegree[i] 0) {q.push_back(i);}}// 储存结果vectorint 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);// 连通
} vectorint 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:vectorint 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(vectorvectorint 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:vectorint 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);}vectorint findRedundantConnection(vectorvectorint 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 vectorint();}
};
1319
先连通看连通块的数量连接 n 个块需要 n - 1 个边
class Solution {
public:vectorint 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, vectorvectorint 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:// 需要维护每个连通块的数量vectorint fa;vectorint 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;}vectorint pondSizes(vectorvectorint land) {// x * col y// 表示八个方向的方向数组vectorvectorint 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);}}}}}}vectorint 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 algorithmclass Solution {
public:// 并查集代码vectorint 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);}vectorvectorstring accountsMerge(vectorvectorstring accounts) {int n accounts.size(); // 账号的数量init(n); // 初始化并查集// 邮箱到账号ID的映射mapstring, 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到邮箱的映射mapint, vectorstring accId_emails;// 遍历所有邮箱账号将它们归类到相同的账号ID下for (auto pair : email_accId) {string email pair.first;int accId find(pair.second); // 获取根账号IDaccId_emails[accId].push_back(email);}// 构建最终的合并后的账户列表vectorvectorstring mergedAccounts;for (auto pair : accId_emails) {int accId pair.first;vectorstring emails pair.second;// 将账号ID添加到前面vectorstring mergedAccount {accounts[accId][0]};sort(emails.begin(), emails.end()); // 对邮箱地址排序mergedAccount.insert(mergedAccount.end(), emails.begin(), emails.end());mergedAccounts.push_back(mergedAccount);}return mergedAccounts; // 返回合并后的账户列表}
};
