当前位置:网站首页>(图论) 连通分量(模板) + 强连通分量(模板)
(图论) 连通分量(模板) + 强连通分量(模板)
2022-06-30 02:35:00 【天赐细莲】
前言
图的联通性是图论中的基础问题之一。
无向图的连通分量通常比较好实现,直接搜索即可。通常方法有:并查集,DFS,BFS
而有向图的强分量的实现与计算则比较困难。通常方法有:tarjan kosaraju
本文不从0开始讲解思路和代码,以展示模板为主,当然强联通分量的算法也可以直接应用于连通分量中
模板题介绍
练习题:
无向图 连通分量
有向图 强连通分量
洛谷:P3387 【模板】缩点
本题是求连通分量的裸题,目的是计算每个联通分量的点的个数
最后求解无法互相到达的点对的对数
注意:
[0,1] 和 [1,0]
视为一对,因此在最后计算时候要2
统计总数时有两种方式
总对数 - 可到达点对数
sum不可到达点对数
本文的代码均用第二种方法
本题并不是求强联通分量的裸题,还要会根据求得的强连通分量进行缩点
根据强连通分量进行缩点
- 重新建图
- 重新设置代表点的点权
- 跑新图搜索答案
连通分量
并查集
并查集天然的能处理无向图的联通性
根据路劲压缩的find就能找到该点的代表点
若对并查集非常熟悉的话,可以在合并的时候一起叠加点数
class UnionFind {
private:
bool flag; // false[0~n-1], true[1~n]
int n;
vector<int> parent;
public:
UnionFind(int n, bool flag = false):n(n), parent(n), flag(flag) {
iota(parent.begin(), parent.end(), 0);
if (flag) {
parent.push_back(n);
}
}
int find(int x) {
// 记忆化,路径压缩
return x == parent[x] ? x : parent[x] = find(parent[x]);
}
void unite(int x, int y) {
// x合并到y中
parent[find(x)] = find(y);
}
int getSccCnt() {
// 统计图中有多少个联通分量
int cnt = 0;
for (int i = flag; i < n + flag; i++) {
cnt += (i == parent[i]);
}
return cnt;
}
};
class Solution {
public:
long long countPairs(int n, vector<vector<int>>& edges) {
UnionFind uf(n);
for (auto& arr : edges) {
uf.unite(arr[0], arr[1]);
}
unordered_map<int ,int> ump;
for (int i = 0; i < n; i++) {
++ump[uf.find(i)];
}
long long sum = 0;
for (auto& [key, val] : ump) {
sum += 1LL * val * (n - val);
}
return sum / 2;
}
};
DFS
常规搜索,这里用
scc[]
顺便代替了vis[]
的作用从AC本题的角度来说,可以在每个搜索中记录遍历的点数,减少后面的统计
scc[]
的步骤,但是还是得有vis[]
的标记
class Solution {
private:
vector<vector<int>> graph; // 无向图
vector<int> scc; // 联通分量,顺便记录vis
void init(int n) {
this->graph.resize(n);
this->scc.resize(n, -1);
}
void dfs(int cur, int top) {
if (scc[cur] != -1) {
return;
}
scc[cur] = top;
for (int& nex : graph[cur]) {
dfs(nex, top);
}
}
public:
long long countPairs(int n, vector<vector<int>>& edges) {
init(n);
// 建立无向图
for (auto& arr : edges) {
graph[arr[0]].emplace_back(arr[1]);
graph[arr[1]].emplace_back(arr[0]);
}
for (int i = 0; i < n; i++) {
if (scc[i] == -1) {
dfs(i, i);
}
}
unordered_map<int, int> ump;
for (int i = 0; i < n; i++) {
++ump[scc[i]];
}
long long sum = 0;
for (auto& [key, val] : ump) {
sum += 1LL * val * (n - val);
}
return sum / 2;
}
};
BFS
同DFS一样
class Solution {
private:
vector<vector<int>> graph; // 无向图
vector<int> scc; // 联通分量,顺便记录vis
void init(int n) {
this->graph.resize(n);
this->scc.resize(n, -1);
}
void bfs(int start, int top) {
queue<int> q;
q.push(start);
scc[start] = top;
while (!q.empty()) {
auto cur = q.front();
q.pop();
for (int& nex : graph[cur]) {
if (scc[nex] == -1) {
scc[nex] = top;
q.push(nex);
}
}
}
}
public:
long long countPairs(int n, vector<vector<int>>& edges) {
init(n);
// 建立无向图
for (auto& arr : edges) {
graph[arr[0]].emplace_back(arr[1]);
graph[arr[1]].emplace_back(arr[0]);
}
for (int i = 0; i < n; i++) {
if (scc[i] == -1) {
bfs(i, i);
}
}
unordered_map<int, int> ump;
for (int i = 0; i < n; i++) {
++ump[scc[i]];
}
long long sum = 0;
for (auto& [key, val] : ump) {
sum += 1LL * val * (n - val);
}
return sum / 2;
}
};
强连通分量
专题:(图论) Tarjan 算法_天赐细莲的博客-CSDN博客
tarjan 算法
思想:
在递归站中的low值相等的点是一个强联通分量
dfn值和low值相等的是该分量的代表点
/** * https://www.luogu.com.cn/problem/P3387 * P3387 【模板】缩点 * * tarjan 求强连通分量 * 然后缩点构造DAG图 */
#include <bits/stdc++.h>
#define int long long
using namespace std;
// tarjan 标配
vector<vector<int>> graph; // 存图
vector<int> dfn; // dfs被访问的时间点
vector<int> low; // 通过回溯可以到达的最早时间点
int timestamp = 1; // 时间戳
// 求强连通分量 标配
vector<int> scc; // 强联通分量
stack<int> stk; // 递归栈
vector<bool> inStk; // 快速辨别是都在递归栈中
void tarjan(int cur) {
dfn[cur] = low[cur] = timestamp++;
stk.push(cur);
inStk[cur] = true;
for (int& nex : graph[cur]) {
if (dfn[nex] == 0) {
// 未访问则搜索一次
tarjan(nex);
low[cur] = min(low[cur], low[nex]);
} else if (inStk[nex]) {
// 在栈中,也要松弛一次
low[cur] = min(low[cur], dfn[nex]);
}
}
// 自己的dfn和low相同,则构成一个强联通分量
if (dfn[cur] == low[cur]) {
int x = -1;
do {
x = stk.top();
stk.pop();
inStk[x] = false;
scc[x] = cur;
} while (x != cur);
}
}
signed main() {
int n, m;
cin >> n >> m;
graph.resize(n + 1);
dfn.resize(n + 1);
low.resize(n + 1);
timestamp = 1;
scc.resize(n + 1, -1);
inStk.resize(n + 1);
vector<int> val(n + 1); // 点权
vector<int> from(m + 1); // 出发点
vector<int> to(m + 1); // 到达点
// 点权
for (int i = 1; i <= n; i++) {
cin >> val[i];
}
// 建图,单向图
for (int i = 1; i <= m; i++) {
cin >> from[i] >> to[i];
graph[from[i]].emplace_back(to[i]);
}
// 跑tarjan 获得强连通分量
for (int i = 1; i <= n; i++) {
if (dfn[i] == 0) {
tarjan(i);
}
}
/** ******** tarjan 跑完,获得强连通分量 ****************************/
/** ******** 根据强连通分量,缩点构造DAG图 ***************************/
// 先将每个强联通分量的点权集中到代表点上
for (int i = 1; i <= n; i++) {
if (scc[i] != i) {
// 代表点不用重复加
val[scc[i]] += val[i];
}
}
unordered_map<int, vector<int>> dagGraph;
for (int i = 1; i <= m; i++) {
int &u = from[i], &v = to[i];
// 不在一个分量中
if (scc[u] != scc[v]) {
dagGraph[scc[u]].emplace_back(scc[v]);
}
}
function<int(int)> dfsDag = [&](int cur) -> int {
int sum = 0;
for (int& nex : dagGraph[cur]) {
// 获得子树的最大值,还可以记忆化优化下
sum = max(sum, dfsDag(nex));
}
return val[cur] + sum;
};
int maxx = 0;
// 遍历每个点,可能有某点的是单独的分量没有边
for (int i = 1; i <= n; i++) {
if (scc[i] == i) {
maxx = max(maxx, dfsDag(scc[i]));
}
}
cout << maxx << endl;
return 0;
}
kosaraju 算法
另一种求强连通分量的方法
- 建立正向和反向图
- 先dfs反向图
- 在正向图中逆序dfs反向图的结果,并记录每个点在哪个联通分量中
/** * https://www.luogu.com.cn/problem/P3387 * P3387 【模板】缩点 * * kosaraju 求强连通分量 * 然后缩点构造DAG图 */
#include <bits/stdc++.h>
#define int long long
using namespace std;
// kosaraju 标配
vector<vector<int>> forwardGraph; // 正向图
vector<vector<int>> reverseGraph; // 反向图
vector<int> scc; // 强连通分量
vector<int> vis; // vis标记
stack<int> stk; // 反图入栈
void reverseDFS(int cur) {
vis[cur] = true;
for (int& nex : reverseGraph[cur]) {
if (!vis[nex]) {
reverseDFS(nex);
}
}
// 访问的点依次入栈
stk.push(cur);
}
void forwardDFS(int cur, int father) {
vis[cur] = true;
scc[cur] = father; // 记录是哪个强连通分量
for (int& nex : forwardGraph[cur]) {
if (!vis[nex]) {
forwardDFS(nex, father);
}
}
}
signed main() {
int n, m;
cin >> n >> m;
forwardGraph.resize(n + 1);
reverseGraph.resize(n + 1);
scc.resize(n + 1);
vis.resize(n + 1);
vector<int> val(n + 1); // 点权
vector<int> from(m + 1); // 出发点
vector<int> to(m + 1); // 到达点
// 记录点权
for (int i = 1; i <= n; i++) {
cin >> val[i];
}
// 正向反向图同时建立
for (int i = 1; i <= m; i++) {
cin >> from[i] >> to[i];
forwardGraph[from[i]].push_back(to[i]);
reverseGraph[to[i]].push_back(from[i]);
}
fill(vis.begin(), vis.end(), false);
// 反向图遍历
for (int i = 1; i <= n; i++) {
if (!vis[i]) {
reverseDFS(i);
}
}
fill(vis.begin(), vis.end(), false);
// 逆序遍历反向图的结果
// 目的是获得强连通分量scc
while (!stk.empty()) {
int cur = stk.top();
stk.pop();
if (!vis[cur]) {
forwardDFS(cur, cur);
}
}
/** ************** kosaraju 跑完,获得强连通分量 *********************/
/** ******** 根据强连通分量,缩点构造DAG图 ***************************/
// 先将每个强联通分量的点权集中到代表点上
for (int i = 1; i <= n; i++) {
if (scc[i] != i) {
// 代表点不用重复加
val[scc[i]] += val[i];
}
}
unordered_map<int, vector<int>> dagGraph;
for (int i = 1; i <= m; i++) {
int &u = from[i], &v = to[i];
// 不在一个分量中
if (scc[u] != scc[v]) {
dagGraph[scc[u]].emplace_back(scc[v]);
}
}
function<int(int)> dfsDag = [&](int cur) -> int {
int sum = 0;
for (int& nex : dagGraph[cur]) {
// 获得子树的最大值,还可以记忆化优化下
sum = max(sum, dfsDag(nex));
}
return val[cur] + sum;
};
int maxx = 0;
// 遍历每个点,可能有某点的是单独的分量没有边
for (int i = 1; i <= n; i++) {
if (scc[i] == i) {
maxx = max(maxx, dfsDag(scc[i]));
}
}
cout << maxx << endl;
return 0;
}
END
边栏推荐
- [NPM] solve the problem of error reporting when installing typeorm with NPM
- Global and Chinese markets for light cargo conveyors 2022-2028: Research Report on technology, participants, trends, market size and share
- Alphassl digital certificate
- What are the requirements for NPDP product manager international certification examination?
- IBM websphere通道联通搭建和测试
- 2022 the action of protecting the net is imminent. Things about protecting the net
- 冒泡排序
- DigiCert Smart Seal是什么?
- How do PMP candidates respond to the new exam outline? Look!
- Recursion frog jumping steps problem
猜你喜欢
Differences among digicert, SECTIONO and globalsign code signing certificates
LeetCode 3. 无重复字符的最长子串
SiteLock九个常见问题
Digicert、Sectigo、Globalsign代码签名证书的区别
How vscode debugs into standard library files / third-party package source code
归并排序
Insert sort directly
Recursion frog jumping steps problem
A quick look at the statistical data of 23 major cyber crimes from 2021 to 2022
1380. lucky numbers in matrices
随机推荐
How to use SMS to deliver service information to customers? The guide is here!
新考纲下的PMP考试有多难?全面解析
代码签名、驱动签名的常见问题解答
SQLite使用
What is certificate transparency CT? How to query CT logs certificate logs?
How do PMP candidates respond to the new exam outline? Look!
What is an X.509 certificate? 10. 509 certificate working principle and application?
选择排序
What are the requirements for NPDP product manager international certification examination?
Linear algebra Chapter 4 Summary of knowledge points of linear equations (Jeff's self perception)
Bucket sort
Enlightenment from the revocation of Russian digital certificate by mainstream CA: upgrade the SSL certificate of state secret algorithm to help China's network security to be autonomous and controlla
Global and Chinese markets for light cargo conveyors 2022-2028: Research Report on technology, participants, trends, market size and share
银行的理财产品一般期限是多久?
How to display all keys through redis cli- How to show ALL keys through redis-cli?
FDA ESG规定:必须使用数字证书保证通信安全
DHU programming exercise
Heap sort
CMake教程系列-02-使用cmake代码生成二进制
主流CA吊销俄罗斯数字证书启示:升级国密算法SSL证书,助力我国网络安全自主可控