PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: gunpoint_88
Tester & Editorialist: iceknight1093
DIFFICULTY:
2830
PREREQUISITES:
Graphs, finding connected components
PROBLEM:
N people are lost in a forest, each with their own radios.
Person i's radio can transmit K_i frequencies, given as a list F_i = [f_{i, 1}, f_{i, 2}, \ldots, f_{i, K_i}]
Two people a and b can communicate with each other if they either share a common frequency (i,e F_a \cap F_b \neq \emptyset), or there exists a person c who can communicate with both of them.
In one operation, you can move a frequency from one person’s radio to another.
That is, choose i and j, and an element x \in F_i. Then, delete x from F_i and append x to F_j.
Find the minimum number of operations to reach a state where everyone can communicate with everyone else; or claim that it is impossible.
EXPLANATION:
The condition on two people being able to communicate sounds suspiciously similar to connectivity in a graph (two vertices are connected if they either have a direct edge between them, or if there’s some other vertex that is connected to both of them).
This should hint you towards thinking about graphs.
Let C be the total number of distinct frequencies present in the input.
Consider an undirected bipartite graph on N+C vertices, where:
- There are N vertices on the left, representing the people
- There are C vertices on the right, representing the frequencies
- There’s an edge between i on the left and j on the right if person i's radio can transmit frequency j.
This graph has exactly \sum_{i=1}^N K_i edges, so creating and storing it isn’t an issue since the sum of K_i across all testcases is small enough.
Now, note that person i and person j can communicate with each other if and only if they lie in the same connected component of this graph.
Proof
Suppose person a and person b are in the same component. Then, there must exist a path a = x_1 \to y_1 \to x_2 \to y_2 \to \ldots \to x_{k-1} \to y_{k-1} \to x_k = b of even length (since the graph is bipartite), where each x_i is a person and each y_i is a frequency.
Via this path, clearly for each 1 \leq i \lt k person x_i can communicate with person x_{i+1} via frequency y_i, since they can both transmit it.
Chaining this relation allows person a to communicate with person b.
Conversely, suppose person a and person b can communicate with each other.
Then, either a and b can communicate directly (in which they’re surely in the same component), or there must exist a sequence of people x_1, x_2, \ldots, x_k such that:
- a can communicate with x_1 directly (i.e they share a frequency)
- x_i can communicate with x_{i+1} directly for each i
- x_k can communicate with b directly
Putting all this together means a and b must lie in the same component, as claimed.
So, our aim is to ensure that all N people end up in the same component.
As for the operation we perform, moving a frequency from one person to another translates to shifting the ‘left’ endpoint of the corresponding edge, while the ‘right’ endpoint remains the same.
Let’s look at how moving an edge like this affects connectivity.
Suppose we move frequency x from person i to person j, i.e, replace the edge i \leftrightarrow x with j \leftrightarrow x.
This can be thought of as deleting one edge and adding a new one.
Note that:
- Removing an edge either keeps the number of components the same, or increases it by 1
In particular, if the edge is a bridge (doesn’t lie on a cycle), the number of components will increase by 1; otherwise the number of components will not change. - Adding an edge either keeps the number of components the same, or decreases it by 1
In particular, if the edge joins vertices from two different components then the component count reduces by 1; else it doesn’t change.
So, an operation is only ‘useful’ (i.e, decreases the number of components) if the removal stage keeps the number of components the same, while the addition stage decreases it by 1.
That is, an operation must take an edge that lies on a cycle and use it to join two different components.
The second part is quite simple: we’re free to choose the left endpoint, so we can always choose a vertex not in the current component.
Dealing with the first part is seemingly trickier, but is in fact not that hard either.
Consider some connected component with X vertices and Y edges.
Fix a spanning tree of this component, which uses X-1 of these Y edges.
This leaves us with Y - (X-1) ‘free’ edges, which can certainly be used to connect to other components.
Suppose there are W components in total, and let f be the total number of free edges across all these components.
If f \geq W-1, we can directly use W-1 free edges to connect all the components (and doing it in less than W-1 operations is clearly impossible).
On the other hand, if there are less than W-1 free edges then it’s impossible to connect all the components!
Proof
Suppose f \lt W-1.
Then, the total number of edges we have is N+C-W+f. This is because:
- There are N+C vertices.
- A spanning forest of these vertices with W components uses exactly N+C-W edges.
- Then, there are f free edges.
If f \lt W-1, then N+C-W+f \lt N+C-W+W-1 = N+C-1, i.e, there are strictly less than N+C-1 edges in total.
It’s impossible to connect N+C vertices with less than N+C-1 edges.
Note that if all N people are in the same component, then the graph as a whole must be connected because we can’t change the right endpoints of the edges (so each frequency is connected to at least one person, and hence to all the people).
This means we’d like to end up with a connected graph on N+C vertices, but simply can’t.
This gives us a pretty simple solution:
- Construct the graph mentioned above, and compute W and f: its number of components and free edges.
- If f \geq W-1, the answer is W-1.
Note that this is equivalent to checking whether the number of edges is at least N+C-1, so in fact there’s no need to even compute the free edges. - Otherwise, it’s impossible.
Counting components can be done in linear time with DFS/BFS (or use a DSU for technically worse complexity but same speed in-practice), so we’re done.
TIME COMPLEXITY
\mathcal{O}(N+\sum K_i) per test case.
CODE:
Author's code (C++)
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#ifdef ANI
#include "D:/DUSTBIN/local_inc.h"
#else
#define dbg(...) 0
#endif
class dsu{
public:
int N;
vector<int> par,size;
dsu(int N) {
this->N=N; par=size=vector<int>(N,1);
for(int i=0;i<N;i++)
par[i]=i;
}
int find(int u) {
return par[u]==u?u:par[u]=find(par[u]);
}
int join(int u,int v) {
u=find(u),v=find(v);
if(u==v) return 0;
if(size[u]<size[v]) swap(u,v);
par[v]=u; size[u]+=size[v]; return 1;
}
};
int main() {
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int t;
cin>>t;
while(t--) {
int n,ect=0; cin>>n;
vector<int> u;
vector<vector<int>> frq(n);
for(int i=0;i<n;i++) {
int k; cin>>k;
ect+=k;
while(k--) {
int x; cin>>x;
u.push_back(x);
frq[i].push_back(x);
}
}
sort(u.begin(),u.end());
u.resize(unique(u.begin(),u.end())-u.begin());
int m=u.size();
if(ect<n+m-1) {
cout<<-1<<"\n";
continue;
}
dsu D(n+m);
for(int i=0;i<n;i++) {
for(int f:frq[i]) {
int k=lower_bound(u.begin(),u.end(),f)-u.begin()+n;
D.join(i,k);
}
}
int ans=-1;
for(int i=0;i<n;i++) {
ans+=(D.find(i)==i);
}
cout<<ans<<"\n";
}
}
Editorialist's code (Python)
import sys
input = sys.stdin.readline
for _ in range(int(input())):
n = int(input())
mapper = {}
id = n
lst = [ [] for _ in range(n) ]
edges = 0
for i in range(n):
lst[i] = list(map(int, input().split()))[1:]
edges += len(lst[i])
for j in range(len(lst[i])):
x = lst[i][j]
if x not in mapper:
mapper[x] = id
id += 1
lst[i][j] = mapper[x]
N = id
graph = [ [] for _ in range(N) ]
for i in range(n):
for x in lst[i]:
graph[i].append(x)
graph[x].append(i)
mark = [0]*N
comps = 0
for i in range(N):
if mark[i] == 1: continue
comps += 1
mark[i] = 1
queue = [i]
for u in queue:
for v in graph[u]:
if mark[v] == 1: continue
mark[v] = 1
queue.append(v)
print(comps - 1 if edges >= N-1 else -1)