Решение с помощью двудольных графов и алгоритма Куна

#include <iostream>
#include <vector>
#include <algorithm>
#include <ranges>
#include <iterator>
#include <numeric>
#include <iomanip>
#include <unordered_set>
namespace rng = std::ranges;
 
std::vector<std::vector<int>> g;    // будем хранить только рёбра из левой доли в правую
std::vector<bool> vUsed;            // вспомогательный массив для поиска пути dfs-ом
std::vector<int> vMatch;            // с какой вершиной сматчена вершина правой доли (-1, если ни с какой)
 
// dfs возвращает, можно ли найти путь из вершины v в какую-нибудь вершину правой доли
// если можно, то ещё и проводит чередование
bool dfs(int v)
{
    if (vUsed[v])
        return false;
    vUsed[v] = true;
    for (size_t i = 0; i < g[v].size(); ++i)
    {
        if (g[v][i] == 1)
        {
            int to = i;
            if (vMatch[to] == -1 || dfs(vMatch[to]))
            {
                vMatch[to] = v;
                return true;
            }
        }
    }
    return false;
}
 
int main()
{
    std::vector<std::unordered_set<std::string>> vj;
    int n{}, k{};
    std::cin >> n;
    g.resize(n);
    rng::for_each(g, [n](auto& v) { v.resize(n); });
    for (int i = 0; i < n; ++i)
    {
        std::cin >> k;
        vj.emplace_back();
        std::copy_n(std::istream_iterator<std::string>{std::cin}, k, std::inserter(vj.back(), vj.back().end()));
    }
    for (int i = 0; i < vj.size(); ++i)
    {
        for (int j = 0; j < vj.size(); ++j)
        {
            if (i != j && rng::all_of(vj[i], [&](auto const& s) {return vj[j].contains(s); }))
            {
                g[i][j] = 1;
            }
        }
    }
 
    vUsed.resize(n, false);
    vMatch.resize(n, -1);
    int maxPairs{};
    for (int i = 0; i < n; ++i)
    {
        std::fill_n(vUsed.begin(), n, false);
        if (dfs(i))
        {
            ++maxPairs;
        }
    }
 
    int cntWash{};
    std::fill_n(vUsed.begin(), n, false);
    for (int i = 0; i < n; ++i)
    {
        if (vUsed[i])
            continue;
        int head = i;
        while (vMatch[head] != -1)
        {
            head = vMatch[head];
        }
 
        while (true)
        {
            vUsed[head] = true;
            auto it = rng::find(vMatch, head);
            if (it == vMatch.end())
                break;
            vUsed[it - vMatch.begin()] = true;
            head = it - vMatch.begin();
        }
        ++cntWash;
    }
    cntWash += rng::count_if(vUsed, [](auto b) {return !b; });
    std::cout << "\ncntWash: " << cntWash << "\n";
}