Phone and Chargers - Editorial

About the Problem

Setter(s) Divyansh Verma
Tester(s) Vichitr Gandas
Difficulty Easy-Medium
Topics Graph, DFS
Practice Link
Contest Link

Solution Idea

Model the problem as a graph problem. If two people are friends, make an edge between them. Now if two persons want to exchange their chargers then they should be in same connected component of the graph. So for each component, find the frequency of each charger type & mobile type using two maps. Then min(freqCharger[x], freqMobile[x]) should be number of people in the component who get the mobile & charger both of type x . This way, run a DFS to form these maps and then iterate over them to add min(freqCharger[x], freqMobile[x]) to the answer for each valid x in freqCharger map. This will give us maximum number of matched phones & chargers.

Complexity Analysis

Time Complexity: \mathcal{O}(n \log{n}) for DFS & maintaining the maps.
Space Complexity: \mathcal{O}(n) for storing graph & maps.

Codes

Setter's Code
#include<bits/stdc++.h>
using namespace std;
#define int long long int

#define V vector<int>
#define MM unordered_map<int,int>
#define P vector<pair<int,int>>

void dfs(int u,vector<V> &graph,V &visit,P &people,MM &Mob){
    if(visit[u]) return;
    visit[u] = true;
    Mob[people[u].first]++; Mob[people[u].second]--;

    for(int v:graph[u]){
        dfs(v,graph,visit,people,Mob);
    }
}

class PhonesAndMobiles {
public:
    int getOutput(){
        int N,m,X; cin>>N>>m>>X;

        P friends,people;
        for(int i=0;i<N;i++){
            int x,y; cin>>x>>y;
            people.emplace_back(x,y);
        }

        for(int i=0;i<m;i++){
            int x,y; cin>>x>>y;
            friends.emplace_back(x,y);
        }

        V visit(N,0);
        MM Mob;

        int ans = 0;
        vector<V> graph(N,V());
        for(int i=0;i<m;i++){
            graph[friends[i].first].push_back(friends[i].second);
            graph[friends[i].second].push_back(friends[i].first);
        }

        for(int i=0;i<N;i++){
            if(!visit[i]){
                Mob.clear();
                dfs(i,graph,visit,people,Mob);
                for(auto x:Mob) ans += abs(x.second);
            }
        }

        assert(ans%2 == 0);
        return ans/2;
    }
};

signed main(){
	PhonesAndMobiles ph;
  	cout<<ph.getOutput()<<endl;
}
Tester's Code
/***************************************************

@author: vichitr
Compiled On: 04 Mar 2021

*****************************************************/
#include<bits/stdc++.h>
#define int long long
#define fast ios::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL)
#define pb push_back

using namespace std;

const int N = 1e5+7;

int n,m,x;
vector<int> adj[N];
int mobile[N], charger[N];

bool vis[N];
map<int, int> mob, cha;

void dfs(int v){
    vis[v] = 1;
    mob[mobile[v]]++;
    cha[charger[v]]++;

    for(int i: adj[v])
        if(!vis[i])
            dfs(i);
}

void solve(){
    cin>>n>>m>>x;
    assert(1 <= n and n <= 1e5);
    assert(1 <= m and m <= 1e5);
    assert(1 <= x and x <= 1e5);
    
    for(int i = 0; i < n; i++) {
        cin>>mobile[i]>>charger[i];
        assert(1 <= mobile[i] and mobile[i] <= x);
        assert(1 <= charger[i] and charger[i] <= x);
    }
    for(int i = 0; i < m; i++) {
        int x,y; cin>>x>>y;
        assert(0 <= x and x < n);
        assert(0 <= y and y < n);
        adj[x].pb(y);
        adj[y].pb(x);
    }

    int ans = 0;
    for(int i=0;i<n;i++){
        if(!vis[i]){
            mob.clear();
            cha.clear();
            dfs(i);
            for(auto i: mob){
                ans += min(cha[i.first], i.second);
            }
        }
    }

    cout<<n-ans;
}

signed main()
{
    fast;
    int t=1;
    // cin >>t;
    assert(t <= 1e5);
    for(int i=1;i<=t;i++)
    {
        solve();

    }
    return 0;
}

If you have used any other approach, share your approach in comments! If you have any doubts, ask them in comments!

3 Likes