Problem Link
Algorithms used: DSU, greedy, DFS
In this problem, we are given an undirected weighted graph and we need to choose a subset of nodes such that they form a simple cycle and the edge with the smallest weight is the smallest edge that can be included in any simple cycle.
A straightforward solution would sort the edges in increasing order of weight and then check if that edge can be included in a simple cycle by running a DFS from one of the endpoints of the edge and checking if the other endpoint can be reached. However, this could take O(M²) time since we might traverse all the edges of the graph every time we run the DFS.
We can use a DSU to figure out what edge completes a cycle by checking if the endpoints of the edge that we are are trying the add to the DSU are already connected. Once we find this edge we can run the DFS described above just once to figure out the subset of nodes that form the cycle. We would like this edge to be the one with the smallest weight so that we can guarantee that the cycle will contain this edge.
The only problem is finding out this edge. To solve this problem we make a careful observation: edges with larger weights don't affect the answer. So we sort the edges in decreasing order of edge weights and add the edges to the DSU until we come across an edge that "completes" the cycle. There could be multiple such edges, so we pick the one with the smallest edge.
Code
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector <vector <int>> adj;
vector <int> cycle;
vector <bool> vis;
struct DSU {
vector <int> link, sz;
DSU (int s) {
link = sz = vector <int> (s+1);
for (int i = 1; i <= s; i++) {
link[i] = i;
sz[i] = 1;
}
}
int head(int x) {
while (x != link[x])
x = link[x];
return x;
}
bool same(int a, int b) {
return head(a) == head(b);
}
void unite(int a, int b) {
a = head(a);
b = head(b);
if (sz[a] < sz[b])
swap(a, b);
sz[a] += sz[b];
link[b] = a;
}
};
bool comp(vector <int> a, vector <int> b) {
return a[2] > b[2];
}
bool dfs(int s, int p, int goal) {
if (s == goal) {
cycle.push_back(s);
return true;
}
if (vis[s])
return false;
vis[s] = true;
cycle.push_back(s);
for (auto i : adj[s]) {
if (i == p || (s == p && i == goal))
continue;
if (dfs(i, s, goal)) {
return true;
}
}
cycle.pop_back();
return false;
}
int main() {
int T;
cin >> T;
while (T--) {
int n, m;
cin >> n >> m;
adj = vector <vector <int>> (n+1);
vis = vector <bool> (n+1);
vector <vector <int>> edges;
cycle.clear();
for (int i = 0; i < m; i++) {
int a, b, w;
cin >> a >> b >> w;
if (a > b)
swap(a, b);
vector <int> v = {a, b, w};
edges.push_back(v);
}
sort(edges.begin(), edges.end(), comp);
int st = 0, ed = 0, answ = 1e9;
DSU dsu(n+1);
for (int i = 0; i < m; i++) {
int a = edges[i][0], b = edges[i][1], w = edges[i][2];
if (dsu.same(a, b)) {
st = a, ed = b, answ = w;
} else {
dsu.unite(a, b);
adj[a].push_back(b);
adj[b].push_back(a);
}
}
dfs(st, st, ed);
cout << '\n';
cout << answ << ' ' << cycle.size() << '\n';
for (auto i : cycle)
cout << i << ' ';
cout << '\n';
cout << '\n';
}
}
Comments