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

P3388 Template — Cut Vertex (Cut Vertex) — Luogu | The New Ecosystem of Computer Science Education (luogu.com.cn)

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.

1. When there is a solution, $$$m$$$ must have an upper and lower bound, the lower bound is $$$m \ge n-1$$$;
2. $$$v$$$ has already connected $$$n-1$$$ points, cannot have duplicate edges, so $$$v$$$ cannot connect any more, regarded as $$$v$$$ does not exist;
3. 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$$$;
4. Leave $$$1$$$ single point connected only with $$$v$$$, and the remaining $$$n-2$$$ points construct a complete graph;
5. 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

P3469 BLO-Blockade

• 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;
}