Critical Links (UVa 796)

Today, I’ll walk you through solving UVa 796 - Critical Links 

What Are Critical Links?

A critical link in a graph is an edge that, if removed, increases the number of connected components of the graph. These edges play a vital role in maintaining the graph's connectivity and can be used in network reliability analysis or circuit design.

Problem Overview

The problem asks us to find all critical links in a bidirectional graph

Solution

To solve this problem we can use Tarjan's Algorithm for finding bridges works using DFS. It maintains two critical arrays:

• disc[]: Records the discovery time of each node during the DFS.
• low[]: Tracks the lowest discovery time reachable from a node.

The key insight is that an edge (u, v) is a critical link if and only if low[v] > disc[u] after exploring v.

Key Steps in Tarjan’s Algorithm

1. Perform a DFS traversal starting from an unvisited node.
2. Update disc[] and low[] arrays as you visit nodes.
3. For each edge (u, v), check if removing it disconnects the graph by comparing low[v] and disc[u].
4. Collect all such edges as critical links.

Implementation

Here’s the solution I wrote for UVa 796:

// time-limit: 1000
// problem-url: https://onlinejudge.org/external/7/796.pdf
#include <bits/stdc++.h>

using namespace std;

#ifdef DEBUG
#include <algo/debug.h>
#else
#define debug(...) 42
#endif

void dfs(int u, int parent, const vector<vector<int>>& adj, 
    vector<bool>& vis, vector<int>& disc,
    vector<int>& low, vector<pair<int, int>>& critical_links, int& time) {
  vis[u] = true;
  disc[u] = low[u] = ++time;
  for (int v : adj[u]) {
    if (!vis[v]) {
      dfs(v, u, adj, vis, disc, low, critical_links, time);
      low[u] = min(low[u], low[v]);
      if (low[v] > disc[u]) {
	critical_links.emplace_back(min(u, v), max(u, v));
      }
    } else if (v != parent) {
      low[u] = min(low[u], disc[v]);
    }
  }
}

int main (void) {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n; 

  while (cin>>n) {
    vector<vector<int>> adj(n, vector<int>());
    for (int i = 0; i < n; ++i) {
      int u, v, w; char c;
      cin>>u>>c>>w>>c;
      for (int j = 0; j < w; ++j) {
	cin>>v;
	adj[u].push_back(v);
      }
    }
    vector<bool> vis(n, false);
    vector<int> low(n, -1), disc(n, -1);
    vector<pair<int, int>> critical_links;
    int time = 0;
    for (int i = 0; i < n; ++i) {
      if (!vis[i]) {
	dfs(i, -1, adj, vis, disc, low, critical_links, time);
      }
    }
    sort(critical_links.begin(), critical_links.end());
    cout << critical_links.size() << " critical links\n";
    for (int i = 0; i < critical_links.size(); ++i) {
      cout << critical_links[i].first << " - " << critical_links[i].second << '\n';
    }
    cout << '\n';
  }

  return 0;
}

Explanation of the Code

1. Input Parsing:
   • Each node specifies the number of connections it has.
   • Adjacency lists are built accordingly.
2. DFS Initialization:
   • Arrays like disc[], low[], and visited[] are initialized.
   • Each connected component of the graph is explored.
3. DFS Logic:
   • The discovery time (disc[]) and the lowest reachable node (low[]) are updated during the traversal.
   • If low[v] > disc[u], the edge (u, v) is identified as a critical link.
4. Output Formatting:
   • Critical links are stored in lexicographical order using min(u, v) and max(u, v).
   • They are sorted and printed at the end.

Example Walkthrough

Input:

5
0 (2) 1 2
1 (2) 0 2
2 (3) 0 1 3
3 (1) 2 4
4 (1) 3

Output:

2 critical links
2 - 3
3 - 4

Here, removing edge 2-3 or 3-4 increases the number of connected components, so they are critical links.

Complexity Analysis

• Time Complexity: O(V + E), where V is the number of vertices and E is the number of edges. This is due to the DFS traversal.
• Space Complexity: O(V + E) for adjacency lists and auxiliary arrays.

Corner Cases

• Remember that the provided graph is not necessarily connected
• To ensure consistent output formatting and avoid potential grammatical issues, always use the plural form "links" in the line "<n> critical links", even when there is only one critical link.
• The input no_of_servers = 0 does not always indicate the end of the input, which is a common convention in many other UVa problems.