Author: SQU_Test
DIFFICULTY:
Medium
PREREQUISITES:
Graph, MST.
PROBLEM:
Omar is attending an algorithms course and today they had a lecture about graphs. He wants to practice on some graph problems and he come across a description of a graph “It is an undirected weighted graph on n vertices. It is a complete graph: each pair of vertices is connected by an edge. The weight of each edge is either 0 or 1; exactly m edges have weight 1, and all others have weight 0”.
Omar decides to find the weight of the minimum spanning tree of the graph. (The weight of a spanning tree is the sum of all its edges.) Can you help Omar find the answer?
EXPLANATION:
First examine the given graph where there are only edges of weight 0: suppose that the number of connected components in this subgraph is k. Then the minimum spanning tree of the given graph is equal to k – 1. Therefore, we need to find the number of such (zero weight) components in the given graph.
The following is a O(m + n log n) solution. Let’s maintain the zero weight components in the disjoint set union, and let’s also store the size of each such component. Then we iterate over all vertices v from 1 to n. Put the vertex v in a new component of size 1. Then we iterate over the weight 1 edges {u, v} such that u < v. For each of the zero weight components, we count the number of edges from this component to v. If the number of such edges is less than the size of the component of u, we should merge the component of u with v (because there is at least one 0 weight edge between this component and v). Otherwise we should not merge the component with v. In the end, we get the number of zero weight components.
TIME COMPLEXITY:
In total, n new components are created in the course of the algorithm (a new one for each of the n vertices). When we merge some old component with v, the number of components decreases by 1. Thus, the total number of such cases during the algorithm is at most O(n), and for each we have one merge call for DSU. This part has O(n log n) complexity.
When we don’t merge an old component with v, there is at least one edge of weight 1 from this component to v. Therefore, the total number of such cases is at most the number of edges, m. Thus, the complexity of processing these cases is O(m).
Hence, the total complexity of the algorithm is $O(n log n + m).
SOLUTIONS:
source
Solution using DSU
#include<iostream>
#include<vector>
#include<algorithm>
#include <numeric>
using namespace std;
struct DSU {
int n;
vector<int> uf;
DSU(int n): n(n) {
uf.assign(n, -1);
}
int find(int x) {
return uf[x] < 0 ? x : (uf[x] = find(uf[x]));
}
int merge(int x, int y) {
int xr = find(x);
int yr = find(y);
if (xr == yr)
return 0;
if (uf[yr] < uf[xr]) {
uf[yr] += uf[xr];
uf[xr] = yr;
}
else {
uf[xr] += uf[yr];
uf[yr] = xr;
}
return 1;
}
int get_size(int x) {
return -uf[find(x)];
}
vector<vector<int>> get_comps() {
vector<vector<int>> comps;
vector<int> comp_id(n, -1);
for (int i = 0; i < n; ++i) {
int root = find(i);
if (comp_id[root] == -1) {
comp_id[root] = comps.size();
comps.push_back(vector<int>());
}
comps[comp_id[root]].push_back(i);
}
return comps;
}
};
const int MAXN = 100005;
int n, m;
vector<int> graph[MAXN];
int hop[MAXN];
int fast() {
DSU dsu(n);
int cc = n;
iota(hop, hop + n, 0);
for (int i = 0; i < n; ++i) {
if (graph[i].empty()) return 0;
if (graph[i][0] != 0) {
hop[0] = max(hop[0], graph[i][0] - 1);
cc -= dsu.merge(i, 0);
}
for (int j = 1; j < graph[i].size(); ++j) {
if (graph[i][j - 1] + 1 < graph[i][j]) {
hop[graph[i][j - 1] + 1] = max(hop[graph[i][j - 1] + 1], graph[i][j] - 1);
cc -= dsu.merge(i, graph[i][j - 1] + 1);
}
}
if (!graph[i].empty() && graph[i].back() < n - 1) {
hop[graph[i].back() + 1] = max(hop[graph[i].back() + 1], n - 1);
cc -= dsu.merge(i, graph[i].back() + 1);
}
}
int j = 0;
for (int i = 0; i < n; ++i) {
if (j < i) {
j = i + 1;
}
while (j <= hop[i]) {
cc -= dsu.merge(i, j++);
}
}
return cc - 1;
}
int main() {
cin >> n >> m;
for (int i = 0; i < m; ++i) {
int u, v;
cin >> u >> v;
--u; --v;
graph[u].push_back(v);
graph[v].push_back(u);
}
for (int i = 0; i < n; ++i) {
sort(begin(graph[i]), end(graph[i]));
}
cout << fast() << '\n';
return 0;
}
Solution using DFS
#include<iostream>
#include<vector>
#include<set>
using namespace std;
int n;
set<int> s;
vector<set<int>> g;
void dfs(int u) {
s.erase(u);
vector<int> q;
for (int v : s)
if (!g[u].count(v))
q.push_back(v);
for (int v : q)
s.erase(v);
for (int v : q)
dfs(v);
}
int main() {
int m, u, v;
cin >> n >> m;
g = vector<set<int>>(n);
s = set<int>();
for (int i = 0; i < n; i++) s.insert(i);
for (int i = 0; i < m; i++) {
cin >> u >> v; u--; v--;
g[u].insert(v);
g[v].insert(u);
}
int k = 0;
while (!s.empty()){
k++; dfs(*s.begin());}
cout << k-1 <<endl;
return 0;
}