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.

Maxim and Restaurant (Part 2)

Maxim and Restaurant (Part 1)

In previous post I discussed a O(n ^ 3 * k) solution. Today, I'm going to discuss how we can reduce the complexity to O(n ^ 2 * k). Basically if we see the problem from a different angle we don't need to run our DP for each blocker.

For n persons in queue, we have n! permutations. Lets consider the number of permutations for which we can allow only one person is p1, number of permutations for which we can allow two persons is p2, and so on.

So expected number of persons -
$e = \frac{p1 * 1 + p2 * 2 + ... pn * n}{n!}$

Which can be represented as -
$e = \frac{(p1 + p2 + ... + pn) + (p2 + p3 + ... + pn) + ... + (pn)}{n!}$

Here, p1 + p2 + ... + pn actually represents the number of ways where we can allow at least 1 persons. Lets call it m1. Similarly, p2 + p3 + .. + pn represents number of ways where we can allow at least 2 persons, which is m2 and so on.

So our equation is now -
$e = \frac{m1 + m2 + ... + mn}{n!}$
$=> e = \frac{m1}{n!} + \frac{m2}{n!} + \frac{m2}{n!}$
$=> e = f1 + f2 + .. + fn$

Here, fi = probability of allowing at least i persons.

In last post, in our dynamic programming has states dp[i][j]. In dp[i][j], we calculated probability of having sum j by adding first i persons. For a given k, if we add up all dp[k][j] for all 1 <= j <= p, we'll find the probability of allowing at least k persons. So by removing the blocker and running the dynamic programming algorithm only once we can simply calculate f1, f2, .. fn, and by adding these values, we can get our result.

So here is the simplified code -

public void solve(int testNumber, InputReader in, OutputWriter out) {
        int n = in.readInt();
        int[] a = new int[n];
        int total = 0;
        for (int i = 0; i < n; ++i) {
            a[i] = in.readInt();
            total += a[i];
        }
        int p = in.readInt();
        if (total <= p) {
            out.printLine(n);
            return;
        }

        double res = 0.;
        double[][] dp = new double[n + 1][p + 1];
        dp[0][0] = 1.0;
        for (int i = 0; i < n; ++i) {
            int cur = a[i];
            for (int oldCount = n - 1; oldCount >= 0; --oldCount) {
                for (int oldSum = 0; oldSum + cur <= p; ++oldSum) {
                    dp[oldCount + 1][oldSum + cur] += dp[oldCount][oldSum] / (n - oldCount) * (oldCount + 1);
                }
            }
        }

        for (int count = 1; count <= n; ++count) {
            for (int size = 0; size <= p; ++size) {
                res += dp[count][size];
            }
        }
        out.printLine(res);
    }