Rare
 0/12

BCCs and 2CCs

Authors: Benjamin Qi, Mihnea Brebenel

2-Edge-Connected Components

StatusSourceProblem NameDifficultyTags
YSEasy
Show Tags2CC

C++

#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 3e5;
int timer; // Time of entry in node
int scc; // Number of strongly connected components
int id[MAX_N];
int low[MAX_N]; // Lowest ID in node's subtree in DFS tree
vector<int> neighbors[MAX_N];

This section is not complete.

Any help would be appreciated! Just submit a Pull Request on GitHub.

(implementation)

With DSU

StatusSourceProblem NameDifficultyTags
PlatinumNormal
Show TagsMerging

The analysis for the above problem mentions an O(mα(n))\mathcal{O}(m\alpha(n)) solution. Although this is not a two-connected component problem, we can in fact use DSU to generate two-connected components.

This section is not complete.

Any help would be appreciated! Just submit a Pull Request on GitHub.

(explanation?)

The DSU operations take O(logn)\mathcal{O}(\log n) rather than O(α(n))\mathcal{O}(\alpha(n)) because the DSU does not use union by size, but it's easy to change this.

struct TwoEdgeCC {
struct {
vi e;
void init(int n) { e = vi(n, -1); }
int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); }
bool unite(int x, int y) { // set par[y] = x
x = get(x), y = get(y);
if (x == y) return 0;
e[x] += e[y];
e[y] = x;

Problems

Focus Problem – try your best to solve this problem before continuing!

  • SRM 787 1000

Biconnected Components

Focus Problem – try your best to solve this problem before continuing!

An important observation is that if you can't go from node aa to node bb without passing through node cc, node cc is a critical node (articulation point). Node cc can split aa and bb into 2 different components if removed. This makes us think about biconnected components.

Now we're left with two cases. If node cc isn't critical, a path from aa to bb can avoid the node. Otherwise, if node cc is a critical one we have to check if is on path from aa to bb. Here is a little tricky, on a simple graph, it's not so easy to check, on the other hand, checking this on a tree can be much easier. In order to do this, we transform the graph into a block-cut tree.

In a block-cut tree, every articulation and biconnected component represents a node. Now that we have turned our graph into a tree how do we check if node the path from aa to bb passes through cc? To do this we use LCA. You can find more about this here.

C++

#include <bits/stdc++.h>
using namespace std;
/** @return the block-cut tree of a graph */
vector<vector<int>> biconnected_components(vector<vector<int>> &g,
vector<bool> &is_cutpoint, vector<int> &id) {
int n = (int)g.size();
vector<vector<int>> comps;
vector<int> stk;

Articulation Points

Focus Problem – try your best to solve this problem before continuing!

Resources
CP2

maybe not completely correct

C++

#include <bits/stdc++.h>
using namespace std;
const int NMAX = 2e4;
int timer;
vector<int> low, id;
vector<bool> visited, ap;
vector<vector<int>> g(NMAX);

Problems

StatusSourceProblem NameDifficultyTags
CSESEasy
Show TagsBCC
POINormal
Show TagsBCC
APIONormal
Show TagsBCC
POINormal
Show TagsBCC
TLEHard
Show TagsBCC
CEOIHard
Show TagsBCC
PlatinumVery Hard
Show TagsBCC

Module Progress:

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!