Joints and Bridges in graphs

📌 Table of Contents

1. DFS tree


//DFS tree
int h[maxn],in[maxn],out[maxn],low[maxn];

void DFS(int u, int v)
{
    ++ti;
    in[u]=ti;
    low[u]=ti;
    for(int i:adj[u])
    {
        if(i==v)    continue;
        if(!in[i])
        {
            DFS(i,u);
            low[u]=min(low[u],low[i]);
        }
        else    low[u]=min(low[u],in[i]);
    }
    out[u]=ti;
}
        
Convex vs Concave Convex vs Concave

2. What is a bridge?

Explanation: A bridge is an edge that, when removed it, increases the number of connected components in the graph.

Convex vs Concave

→ Therefore, to check if an edge (u,v) is a bridge, simply check if low(u) = in(u). If so, it is a bridge edge.

3. What is a joint?

Explanation: A joint is a vertex that, when removed along with its incident edges, increases the number of connected components in the graph.

We will divide into 2 cases:

→ With this checking method, we can determine whether a vertex is a joint directly during the DFS process.


bool mark [maxn];
// mark[u] = true means that u is a joint 
void DFS(int u, int v)
{
  int cnt=0;
  ++ti;
  in[u]=low[u]=ti;
  for(int i:adj[u])
  {
  if(i==v)    continue;
  if(!in[i])
    {
      ++cnt;
      DFS(i,u);
      low[u]=min(low[u],low[i]);
      if(v==0 && cnt>1)   mark[u]=true;
      else if(low[i]>=in[u]) mark[u]=true;
    }
    else    low[u]=min(low[u],in[i]);
  }
  out[u]=ti;
}

        

4. Strongly Connected Components (Tarjan's algorigthm)


//SCC - Tarjan's algorithm
void DFS(int u)
{
  in[u] = low[u] = ++ti;
  f.push(u);
  for(int i:adj[u])
  {
    if(deleted[i])  continue;
    if(in[i])   low[u] = min(low[u],in[i]);
    else
    {
      DFS(i);
      low[u] = min(low[u],low[i]);
    }
  }
  if(low[u] == in[u])
  {
    scc++;
    int v;
    do {
      v = f.top();
      f.pop();
      id[v] = scc;
      deleted[v] = true;
    }
    while (v != u);
  }
}

void input()
{
  cin>>n>>m;
  for(int i=1,u,v;i<=m;++i)
  {
    cin>>u>>v;
    adj[u].pp(v);
  }
  for(int i=1;i<=n;++i)
    if(!in[i])  DFS(i);
  cout<<scc;
}

        

5. Problem set