Bridge edges
Let’s talk a little bit about bridges, like in graph theory. In a nutshell, an edge is called a bridge if its removal increases the number of connected components. In a connected graph, if I were to remove a bridge, it would not be connected anymore.
Problem
The problem is 1026 - Critical Links, it’s literally finding bridge edges, it’s a good problem to test your implementation before solving problems where this algorithm is just a part of the solution.
Solution
Next is my implementation in C++:
/* Copyright 2016 Rafael Rendón Pablo <rafaelrendonpablo@gmail.com> */
// region Template
#include <bits/stdc++.h>
using namespace std;
typedef long long int64;
typedef unsigned long long uint64;
const double kEps = 10e-8;
const int kMax = 10005;
const int kInf = 1 << 30;
// endregion
int> graph[kMax];
vector<bool visited[kMax];
int discovery[kMax];
int low[kMax];
void find_bridges(int u, int& t, int p, vector<pair<int, int> >& links) {
true;
visited[u] =
low[u] = t;
discovery[u] = t;
t++;for (int i = 0; i < int(graph[u].size()); i++) {
int v = graph[u][i];
if (!visited[v]) {
find_bridges(v, t, u, links);
low[u] = min(low[u], low[v]);if (low[v] > discovery[u]) {
links.push_back(make_pair(min(u, v), max(u, v)));
}else if (v != p) {
}
low[u] = min(low[u], low[v]);
}
}
}
int main() {
int T;
"%d", &T);
scanf(for (int tc = 1; tc <= T; tc++) {
int n;
"%d", &n);
scanf(for (int i = 0; i < n; i++) {
graph[i].clear();int u, k;
"%d (%d)", &u, &k);
scanf(for (int j = 0; j < k; j++) {
int v;
"%d", &v);
scanf(
graph[u].push_back(v);
}
}"Case %d:\n", tc);
printf(false);
fill(visited, visited + n, 0);
fill(discovery, discovery + n, 0);
fill(low, low + n, int, int> > clinks;
vector<pair<for (int u = 0; u < n; u++) {
if (visited[u]) {
continue;
}int time = 0;
int parent = -1;
find_bridges(u, time, parent, clinks);
}"%ld critical links\n", clinks.size());
printf(
sort(clinks.begin(), clinks.end());for (int i = 0; i < int(clinks.size()); i++) {
"%d - %d\n", clinks[i].first, clinks[i].second);
printf(
}
}return EXIT_SUCCESS;
}
I hope it helps. In the references you can find more detailed explanations of the algorithm.