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.

SGU - 101 - Domino

This is another interesting problem.

Problem link : http://acm.sgu.ru/problem.php?contest=0&problem=101

Problem summery: You're given N (N <= 100) dominoes. Each of the dominoes has two numbers on it between 0 to 6, one in left side and another in right side. You have to arrange all the dominoes in a row so that they touch through equal marked side. If not possible print "No solution". Note that, we also have to check the graph is connected.

For example, we have three dominoes [1 2], [3, 2], [3 4]
If we arrange these dominoes like this -
[1 2] - [3 2] - [3, 4], this is invalid, because right side of first domino and left side of second domino marked with different numbers. But if we flip the second domino, to change left and right side, it will become -
[1 2] - [2 3] - [3 4], now every two adjacent dominoes touches with equal marked side. So it's a valid arrangement. So to organize it like this, we are allowed to rearrange dominoes and rotate any domino.

To solve this problem, we cannot try all possible arrangements because number of arrangements is too large. As the dominoes are marked with numbers between 0 to 6, we can consider we have a graph of 7 nodes named 0 to 6. If there is a domino [a b], we will consider there is an edge between a and b. Now we have a graph of at most 7 nodes and at most 100 edges. Our problem can be described as - is it possible to start traversing from one node and visit each of the edges exactly once?

Let's use the example from the problem. We have 5 dominoes [1 2], [2 4], [2 4], [6 4], [2 1]. We can build our graph like this -



And what about the solution? See the following image, yes we can traverse all edges exactly once.


The path we traversed is 4 -> 2 -> 1 -> 2 -> 4 -> 6. So, our domino arrangement will be, [4 2] - [2 1] - [1 2] - [2 4] - [4 6], if we write the indices of the dominoes this sequence is 2, 5, 1, 3, 4. Note that we flipped one [2 4] tile to [4 2] and [6 4] tile to [4 6]. We also need to output which domino we used as it is by a '+' sign, and which domino we flipped by a '-' sign. So our answer is -
2 -
5 +
1 +
3 +
4 -
Which is also given in the sample output.

Leonhard Euler proved that, we can visit every edge exactly once in a graph if number of nodes having odd degree is not more than two. If number of odd degree in the graph is two, we have to start from one of them and end our tour in another of them. By the name of Euler, this path is called Eulerian trail or Eulerian walk. For example in our graph in the image above, node 4 and 6 have odd degree, so we started at 4 and ended at 6.

So, if the number of odd degree of the graph is more than two, we will output "No solution", otherwise we will try to print any one of the solution, by finding out the Eulerian walk. But, what will be the strategy of our Eulerian walk. We can use the strategy of Fleury's algorithm. The strategy is, start with an odd degree node if there exists any, otherwise start with any node. At each iteration we visit the edge whose deletion would not disconnect the graph.

Now, as we have n edge, so we will remove one edge at each step of our algorithm. We'll try 7 different edges and after removing that edge we'll check whether the graph is connected nor not using a dfs, in our case, which is O(n). So our algorithm is somewhat like O(n * n).

My simple C++ solution -

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>

using namespace std;

bool vis[7];
vector<int> edge_index[7][7];
int degree[7];

// can reach v from u?
bool dfs(int u, int v) {
    if (u == v) {
        return true;
    }
    vis[u] = true;
    for (int i = 0; i <= 6; ++i) {
        if ((edge_index[u][i].size() > 0 || edge_index[i][u].size() > 0)
                && vis[i] == false) {
            if (dfs(i, v)) {
                return true;
            }
        }
    }
    return false;
}

bool is_connected() {
    memset(vis, 0, sizeof(vis));
    for (int i = 0; i <= 6; ++i) {
        if (degree[i]) {
            dfs(i, -1);
            break;
        }
    }    
    for (int i = 0; i <= 6; ++i) {
        if (degree[i] > 0 && vis[i] == false) {
            return false;
        }
    }
    return true;
}

int main (void) {
    int n; // number of dominoes i.e. number of edges
    scanf("%d", &n);
    memset(degree, 0, sizeof(degree));
    for (int i = 0; i <= 6; ++i) {
        for (int j = 0; j <= 6; ++j) {
            edge_index[i][j].clear();
        }
    }
    for (int i = 1; i <= n; ++i) {
        int u, v;
        scanf("%d%d", &u, &v);
        edge_index[u][v].push_back(i);
        degree[u]++;
        degree[v]++;
    }

    int n_odd = 0; // number of nodes with odd degree
    for (int i = 0; i <= 6; ++i) {
        if (degree[i] % 2 == 1) {
            n_odd++;
        }
    }

    if (n_odd > 2 || is_connected() == false) {
        // if number of odd degree node is more than 2
        // eulerian path doesn't exist for this graph
        printf("No solution\n");
    } else {
        int u = -1; // starting node

        // start node with an odd degree node, if exists
        for (int i = 0; i <= 6; ++i) {
            if (degree[i] % 2 == 1) {
                u = i;
                break;
            }
        }

        // if odd degree node not found, start with a node
        // with positive degree, i.e. start with any vertex,
        // which is used in the graph
        if (u == -1) {
            for (int i = 0; i <= 6; ++i) {
                if (degree[i] > 0) {
                    u = i;
                    break;
                }
            }
        }

        // Fleury's algorithm
        // n steps - at each step, remove one edge
        for (int i = 0; i < n; ++i) {
            int selected_ind;
            bool forward_selected;
            for (int j = 0; j <= 6; ++j) {
                if (edge_index[u][j].size() > 0 ||
                    edge_index[j][u].size() > 0) {
                    int cur_ind;
                    bool forward;
                    if (edge_index[u][j].size() > 0) {
                        cur_ind = edge_index[u][j].back();
                        edge_index[u][j].pop_back();
                        forward = true;
                    } else {
                        cur_ind = edge_index[j][u].back();
                        edge_index[j][u].pop_back();
                        forward = false;
                    }
                    degree[u]--;
                    degree[j]--;

                    memset(vis, 0, sizeof(vis));    
                    if (degree[u] == 0 || dfs(u, j) == true) {
                        // remove this edge
                        selected_ind = cur_ind;
                        forward_selected = forward;
                        u = j; // so we are in j now.
                        break;
                    } else {
                        // this edge cannot be removed
                        // back to previous state
                        if (forward) {
                            edge_index[u][j].push_back(cur_ind);
                        } else {
                            edge_index[j][u].push_back(cur_ind);
                        }
                        degree[u]++;
                        degree[j]++;
                    }
                }
            }
            printf("%d %c\n", selected_ind, forward_selected ? '+' : '-');
        }
    }

    return 0;
}