Connectivity Issues
Strong Connectivity and Strong Connectivity Components
- Point biconnected: In an undirected graph, if deleting a point (not $$$x$$$ or $$$y$$$) allows $$$x$$$ and $$$y$$$ to still reach each other, then $$$x$$$ and $$$y$$$ are called point biconnected;
- Edge biconnected: In an undirected graph, if deleting an edge allows $$$x$$$ and $$$y$$$ to still reach each other, then $$$x$$$ and $$$y$$$ are called edge biconnected;
- Property $$$1$$$: Point biconnected does not have transitivity, but edge biconnected does;
- Cut vertex: In an undirected graph $$$G$$$, if deleting $$$x$$$ increases the number of connected components, then $$$x$$$ is called a cut vertex (cut vertex) of $$$G$$$.
- Conclusion: At least $$$3$$$ points are required for an undirected graph to possibly have a cut vertex;
- Cut vertex determination:
- If there is an edge from $$$x$$$ to $$$y$$$ in the search tree, when $$$low_y \ge dfn_x$$$, it means that the minimum timestamp $$$low_y$$$ that $$$y$$$ can reach is above the timestamp of $$$x$$$, $$$y$$$ is "separated" from $$$x$$$ and $$$x$$$ before, $$$x$$$ may be a cut vertex. If $$$x$$$ is not the root of the search tree, or $$$x$$$ is the root, but $$$x$$$ has more than $$$1$$$ child, then $$$x$$$ is a cut vertex.
void tarjan(int x)
{
dfn[x] = low[x] = ++num; //Mark the timestamp
int cnt = 0; //Count the number of child nodes
for (auto& [nxt, w] : nbr[x])
if (!dfn[nxt]) //Not visited $$$nxt$$$
{
tarjan(nxt); //Recursively find
low[x] = min(low[x], low[nxt]); //Maintain the minimum timestamp $$$low_X$$$ that $$$x$$$ can reach
cnt++;
if (low[nxt] >= dfn[x]) //$$$x$$$ may be a cut vertex
if (x != root || cnt >= 2) //Exclude the root node with only $$$1$$$ child
cut[x] = true;
}
else //$$$nxt$$$ has been visited, so $$$nxt$$$ has not yet been backtracked, so $$$low_nxt$$$ cannot be used
low[x] = min(low[x], dfn[nxt]);
return;
}
Example Problems
Luogu P3388
UVA10199
Tourist Guide — Luogu | The New Ecosystem of Computer Science Education (luogu.com.cn)
CF22C
Problem statement: Construct an undirected graph with $$$n$$$ points and $$$m$$$ edges, and point $$$v$$$ must be a cut vertex. Need to handle the case of no solution.
- When there is a solution, $$$m$$$ must have an upper and lower bound, the lower bound is $$$m \ge n-1$$$;
- $$$v$$$ has already connected $$$n-1$$$ points, cannot have duplicate edges, so $$$v$$$ cannot connect any more, regarded as $$$v$$$ does not exist;
- In order to accommodate as many edges as possible, try to connect the complete graph as much as possible, and do not destroy the cut vertex feature of $$$v$$$;
- Leave $$$1$$$ single point connected only with $$$v$$$, and the remaining $$$n-2$$$ points construct a complete graph;
- The upper bound $$$m \le n-1+ (n-2)\times(n-3)/2$$$.
Code:
#include<bits/stdc++.h>
typedef int int32;
#define int long long
using namespace std;
const int N = 1e5 + 5;
int n, m, v;
#define print(x, y) cout << x << ' ' << y << '\n'
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> m >> v;
if (m < n - 1 || m > n - 1 + (n - 2) * (n - 3) / 2)
cout << -1;
else
{
m -= n - 1;
if (v == 1)
{
print(1, 2);
print(1, 3);
for (int i = 3; i < n; i++)
print(i, i + 1);
for (int i = 3; i <= n; i++)
for (int j = i + 2; j <= n; j++)
if (m--)
print(i, j);
else
goto end;//It is not recommended to use `goto`, I am just for convenience.
for (int i = 4; i <= n; i++)
if (m--)
print(i, 1);
else
goto end;
}
else
{
for (int i = 2; i < n; i++)
print(i, i + 1);
print(1, v);
for (int i = 2; i <= n; i++)
for (int j = i + 2; j <= n; j++)
if (m--)
print(i, j);
else
goto end;
}
end:;
}
return 0;
}
Luogu P3469
- A point $$$x$$$, if it is not a cut vertex, its contribution is definitely $$$(n-2) \div 2$$$; otherwise, according to the principle of inclusion-exclusion, the contribution is $$$(n-1)+\sum_{y = A_i}{\left(y \times (n-y)\right)}+(z+1)\times(n-z-1)$$$. Where $$$A_i$$$ is the node $$$i$$$ that satisfies: $$$i$$$ is a child node of $$$x$$$, $$$i$$$ has not been visited before, and $$$low_i >= dfn_x$$$. $$$z$$$ is $$$\sum a_i$$$.
#include<bits/stdc++.h>
typedef int int32;
#define int long long
using namespace std;
const int N = 1e5 + 5;
int n, m, dfn[N], low[N], num, root, ans[N], sum[N];
bool cut[N];
vector<pair<int, int>>nbr[N];
void tarjan(int x)
{
dfn[x] = low[x] = ++num;
sum[x] = 1;
int cnt = 0, tot = 0;
for (auto& [nxt, w] : nbr[x])
if (!dfn[nxt])
{
tarjan(nxt);
sum[x] += sum[nxt];
low[x] = min(low[x], low[nxt]);
cnt++;
if (low[nxt] >= dfn[x])
{
ans[x] += sum[nxt] * (n - sum[nxt]);
tot += sum[nxt];
if (x != root || cnt >= 2)
cut[x] = true;
}
}
else
low[x] = min(low[x], dfn[nxt]);
if (!cut[x])
ans[x] = 2 * (n - 1);
else
ans[x] += (n - tot - 1) * (tot + 1) + (n - 1);
return;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
int x, y, z = 1;
cin >> x >> y;
nbr[x].push_back({ y,z });
nbr[y].push_back({ x,z });
}
for (int i = 1; i <= n; i++)
if (!dfn[i])
root = i, tarjan(i);
for (int i = 1; i <= n; i++)
cout << ans[i] << '\n';
return 0;
}