Point biconnected components
Concept and nature:
Arbitrarily two points in a connected graph, if there are at least two “point-unrepeated” paths between them, it is called a point biconnected component. If any point is removed from this graph, the whole graph is still connected. That is, there is no cut point in vertex biconnected components.
Different point biconnected components have at most one common point, that is, a cut point;
Any cut point is a common point of at least two point biconnected components.
The method of finding the number of biconnected components in an undirected graph:
It is easy to find that when a cut point is found, a visit to a biconnected subgraph of a maximal point has been completed. Then we save the traversed points in the process of DFS, and we can get the biconnected components of this point. It is most reasonable to use a stack to save the DFS access process. In the process of solving the cut point, use a stack to save the traversed edges (Note that it is an edge, not a point,Because the cut point is the common point of biconnected components of multiple points, if the point is pushed into the stack, after the cut point is popped out, only one point biconnected component can be given, and the biconnected components of other points connected to it will be missing this point).
Reference Code:
struct Edge{
int u, v;
Edge(int u=0,int v=0):u(u),v(v){}
}e[maxm];
int n,m,stamp,dfn[maxn],low[maxn],iscut[maxn],bccno[maxn];
int scnt, stack[maxm], bcc_cnt;
vector<int> vec[maxn],bcc[maxn];
void tarjan(int index, int fa)
{
int child=0,tmp;
dfn[index]=low[index]= + + stamp;
for(int i=0;i<vec[index].size();i ++ )
{
tmp=e[vec[index][i]].v;
if(!dfn[tmp])
{
stack[ + + scnt]=vec[index][i],child + + ;
tarjan(tmp, index);
low[index]=min(low[index],low[tmp]);
if(low[tmp]>=dfn[index])
{
iscut[index]=1;
bcc[ + + bcc_cnt].clear();
while(1)
{
int num=stack[scnt--];
if(bccno[e[num].u]!=bcc_cnt)
{
bcc[bcc_cnt].push_back(e[num].u);
bccno[e[num].u]=bcc_cnt;
}
if(bccno[e[num].v]!=bcc_cnt)
{
bcc[bcc_cnt].push_back(e[num].v);
bccno[e[num].v]=bcc_cnt;
}
if(e[num].u==index & amp; & amp; e[num].v==tmp)
break;
}
}
}
else if(dfn[tmp]<dfn[index] & amp; & amp; tmp!=fa)
{
stack[ + + scnt]=vec[index][i];
low[index]=min(low[index], dfn[tmp]);
}
}
if(fa<0 & amp; & amp; child==1)
iscut[index]=0;
}
void find_bcc()
{
// The bccno value of the top cut is meaningless
memset(dfn,0,sizeof(dfn));
memset(low,0,sizeof(low));
memset(iscut,0,sizeof(iscut));
memset(bccno,0,sizeof(bccno));
memset(bcc,0,sizeof(bcc));
stamp=scnt=bcc_cnt=0;
for(int i=1;i<=n;i++)
if(!dfn[i])
tarjan(i,-1);
}
Example: poj 1523
Question: How many cut points are there in a graph? How many biconnected components can each cut point divide the graph into?
Go directly to the code:
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
#define endl '\
'
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 1e3 + 10;
const int INF = 0x3fffffff;
const int mod = 1000000007;
struct Edge {
int v, next;
} edge[maxn * 2];
int head[maxn];
int cnt;
void addedge(int u, int v) {
+ + cnt;
edge[cnt].v = v;
edge[cnt].next = head[u];
head[u] = cnt;
}
int dfn; // dfs traversal order
int num[maxn]; // dfs order of each point
int low[maxn]; // low[v] indicates the smallest num ancestor that v and v's descendants can return
int subnets[maxn]; // point biconnected components of each cut point
bool hasCut; // Whether to find the cut point
int V; // maximum vertex number
int root; // root node
void dfs(int u, int fa) {
int child = 0; // number of unconnected subtrees
num[u] = low[u] = + + dfn; // Record the traversal order of this point, the low value of this point is initially equal to num
for (int i = head[u]; i != -1; i = edge[i].next) {
int v = edge[i].v;
if (!num[v]) {
child ++ ;
dfs(v, u);
low[u] = min(low[u], low[v]); // update the low value with the return value of the descendant
if ((u == root & amp; & amp; child >= 2) || (u != root & amp; & amp; low[v] >= num[u])) { // judge cut point
hasCut = true;
subnets[u] + + ; // Add 1 to the point biconnected component of this cut point
/*
u->v the edge causes u to be a cut point
When dfn[u]==low[v], u->v is an ancestor edge, and u and v are in the same biconnected component
When dfn[u]<low[v], u->v is the cutting edge
The number of connections generated by deleting the cut point u is: the number of connected components where u is located + the number of cut edges connected to u + 1 (edge: fa->u)
*/
}
} else if (v != fa) { // handle fallback edge
low[u] = min(low[u], num[v]);
}
}
}
void solve() {
int u, v, cas = 0;
while (true) {
cnt = 0;
memset(num, 0, sizeof num);
memset(low, 0, sizeof low);
memset(subnets, 0, sizeof subnets);
memset(head, -1, sizeof head);
hasCut = false;
dfn = 0;
V = -1;
while (cin >> u, u) { // build map
cin >> v;
addedge(u, v);
addedge(v, u);
V = max(max(u, v), V);
}
if (V == -1) { // This round of input does not have any vertices, the input ends
return;
}
root = V;
dfs(root, -1); // dfs tarjan
cout << "Network #" << + + cas << endl;
if (hasCut) {
for (int i = 1; i <= V; i ++ ) {
if (subnets[i] > 0) {
cout << "SPF node" << i << "leaves" << subnets[i] + 1 << "subnets" << endl;
}
}
} else {
cout << "No SPF nodes\
";
}
cout << endl;
}
}
int main() {
ios::sync_with_stdio(false);
cin. tie(0);
cout. tie(0);
cout << fixed;
cout. precision(18);
solve();
return 0;
}
Edge double connected components
Concept and nature:
Arbitrarily two points in a connected graph, if there are at least two “edge-unrepeated” paths between them, it is called an edge biconnected component. If any edge is removed from this graph, the whole graph is still connected. That is, there is no cut edge (bridge) in edge biconnected components.
Cut top can only belong to one component, please distinguish it from cut edge.
How many edge biconnected components are there in an undirected graph? At least how many edges should be added to make the biconnected components of any two sides biconnected, that is, the graph G becomes biconnected?
The calculation of edge biconnected components uses the idea of “shrinking points”. It is to regard each side biconnected component as a “shrink point”. The specific implementation is as follows:
(1) First find out all the biconnected components in the graph. In the DFS process, the low value of each point is calculated. Points with the same low value must be in the same side biconnected component (for the definition of low value, see the previous article on cutting points and cutting edges). After the end of DFS, there are as many low values as there are double-connected components.
(2) Treat each edge double-connected component as a point, that is, merge those points with the same low value into a contraction point. These contractions form a tree.
(3) The problem is transformed into: at least how many edges are added to the condensed point tree, so that the tree can be turned into an edge biconnected graph. Because in order to become an edge biconnected graph, the degree of each point must be greater than 1, and it is easy to deduce: At least the number of edges to be increased = (number of nodes with degree 1 + 1)/2.
Example: poj 3352
Question: Given an undirected graph G, there are no multiple edges in the graph. How many edges can be added to make an undirected graph into an edged biconnected graph.
code:
#include <cstdio>
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
#define endl '\
'
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 1e3 + 10;
const int INF = 0x3fffffff;
const int mod = 1000000007;
int n, m, low[maxn], num[maxn], dfn;
vector<int> G[maxn];
int degree[maxn]; // degree of indentation
void dfs(int u, int fa) { // Calculate the low value of each point, points with the same low value must be in the same side biconnected component
low[u] = num[u] = + + dfn;
for (int i = 0; i < G[u].size(); i ++ ) {
int v = G[u][i];
if (!num[v]) {
dfs(v,u);
low[u] = min(low[u], low[v]);
} else if (v != fa) {
low[u] = min(low[u], num[v]);
}
}
}
int tarjan() { // Shrink the biconnected components of each edge, and calculate the degree of each shrink point
memset(degree, 0, sizeof degree);
for (int i = 1; i <= n; i ++ ) { // Treat points with the same low value as a contraction point
for (int j = 0; j < G[i]. size(); j ++ ) {
if (low[i] != low[G[i][j]]) {
degree[low[i]] + + ;
}
}
}
int res = 0;
for (int i = 1; i <= n; i ++ ) { // Count the number of indentations with a degree of 1
if (degree[i] == 1) {
res + + ;
}
}
return res;
}
void solve() {
while (cin >> n >> m) {
memset(num, 0, sizeof num);
memset(low, 0, sizeof low);
for (int i = 1; i <= n; i ++ ) {
G[i].clear();
}
for (int i = 1; i <= m; i ++ ) {
int u, v;
cin >> u >> v;
G[u].push_back(v);
G[v].push_back(u);
}
dfn = 0;
dfs(1, -1);
int ans = tarjan();
cout << (ans + 1) / 2 << endl; // cout << (ans % 2 == 0 ? ans / 2 : ans / 2 + 1) << endl
}
}
int main() {
ios::sync_with_stdio(false);
cin. tie(0);
cout. tie(0);
cout << fixed;
cout. precision(18);
solve();
return 0;
}