Problem Overview

Given n employees and m available languages, each employee may know zero or more languages. Teaching a single language to a single employee costs 1 unit. The task is to determine the minimum total cost required so that every employee can communicate with every other employee (either directly or indirectly).

Understanding Communication

Two employees can communicate if they share a common language. Additionally, if employee A can communicate with employee B, and employee B can communicate with employee C, then employees A and C can communicate indirectly through B.

Consider a sample scenario with 8 employees and 7 languages:

• Employee 1: knows no languages
• Employee 2: knows languages 1, 2, 3
• Employee 3: knows language 1
• Employee 4: knows languages 5, 4
• Employee 5: knows languages 6, 7
• Employee 6: knows language 3
• Employee 7: knows languages 7, 4
• Employee 8: knows language 1

By analyzing shared languages, we can group employees into connected components where everyone can communicate. In this example, there are 3 distinct groups.

To connect these groups, we need to teach atleast one employee from each group a language that another group knows. Each such teaching operation connects one additional group. Therefore, the minimum cost equals the number of groups minus 1.

Special case: If no employee knows any language initially, we need to teach each employee a language, costing n units.

Solution Using Disjoint Set Union

The problem can be efficiently solved using Union-Find (Disjoint Set Union, DSU) data structure:

1. Create two sets for each entity: one for languages (1 to m) and one for employees (m+1 to m+n)
2. For each employee, process all languages they know
3. Union the language with the employee's node in the DSU
4. After processing all employees, count how many employee nodes are their own root (representing separate groups)
5. Return (group count - 1), or n if no languages were known

Implementation

#include <iostream>
#include <vector>
using namespace std;

class UnionFind {
private:
    vector<int> parent;
    
public:
    UnionFind(int size) : parent(size + 1) {
        for (int i = 0; i <= size; i++) {
            parent[i] = i;
        }
    }
    
    int findRoot(int x) {
        if (parent[x] != x) {
            parent[x] = findRoot(parent[x]);
        }
        return parent[x];
    }
    
    void unite(int x, int y) {
        int rootX = findRoot(x);
        int rootY = findRoot(y);
        if (rootX != rootY) {
            parent[rootX] = rootY;
        }
    }
};

int main() {
    int employees, languages;
    cin >> employees >> languages;
    
    UnionFind dsu(languages + employees);
    bool hasLanguage = false;
    
    for (int i = 1; i <= employees; i++) {
        int known;
        cin >> known;
        
        for (int j = 0; j < known; j++) {
            int lang;
            cin >> lang;
            hasLanguage = true;
            // Map language to employee node
            dsu.unite(lang, languages + i);
        }
    }
    
    if (!hasLanguage) {
        cout << employees << endl;
        return 0;
    }
    
    int groups = 0;
    for (int i = languages + 1; i <= languages + employees; i++) {
        if (dsu.findRoot(i) == i) {
            groups++;
        }
    }
    
    cout << (groups - 1) << endl;
    return 0;
}

The algorithm runs in O(n × k × α(n+m)) time, where k is the maximum languages per employee and α is the inverse Ackermann function (practically constant).