Количество подграфов с заданной вершины и степени


Демо:


enter image description here

Есть три вопроса:

  1. Сколько подграфов, чьи Нум(вершин) <= 5 и все вершины имеют два высших образования?

  2. Сколько подграфов, чьи Нум(вершины) == 4 и все вершины имеют 3 степени?

  3. Если добавляется еще два ребра, максимальное число подграфов, который имеет 4 вершины и вершин степени 3. (Для демо выше, \$\бином{2}{5}\$, так что 10 корпусов: {5, 3, 3, 3, 3, 2, 2, 2, 2}, 5 это максимум.


#include <iostream>
#include <utility>
#include <algorithm>
#include <vector>

const int ADD =  1;
const int DELETE = 0;

using std::vector;
using std::cout;
using std::transform;
using std::make_move_iterator;
using std::begin;
using std::max_element;
using std::initializer_list;
using std::end;
using std::find;
using std::move;
using std::back_inserter;

using v1d = vector<int>;
using v2d = vector<vector<int>>;
using v3d = vector<vector<vector<int>>>;

template class vector<int>; // useful for debugger
template class vector<vector<int>>;
template class vector<vector<vector<int>>>;

v2d graph;

void testVertice(const v1d& vertice);
void testSubsets(const v3d& subsets);
void testSubset(const v2d& subsets);

int countDegree(const v2d& v2)
{
    int degree = 0;
    for (const auto& x : v2)
            degree += count(begin(x) + 1, end(x), 1);
    return degree;
}

void buildGraph()
{
    graph =
    {
        {1, 0, 1, 1, 0, 0, 0},
        {2, 1, 0, 1, 1, 1, 0},
        {3, 1, 1, 0, 1, 1, 0},
        {4, 0, 1, 1, 0, 1, 1},
        {5, 0, 1, 1, 1, 0, 1},
        {6, 0, 0, 0, 1, 1, 0}
    };
}

template<typename T, typename TPP>
void generateSubsets(int i, int l, int r, T& temp, TPP& ans, const T& graph_) // make subsets, rather than subgraphs
{
    if (i == graph_.size())
    {
        if (temp.size() >= l && temp.size() < r)
            ans.push_back(temp);
        return;
    }

    generateSubsets(i+1, l, r, temp, ans, graph_);
    temp.push_back(graph_[i]);
    generateSubsets(i+1, l, r, temp, ans, graph_);
    temp.pop_back();
}



void repairSubsets(v3d& ans) //remove redundent degrees in graphs.
{
    for(v2d& subset : ans)
    {
        v1d points;

        transform(begin(subset), end(subset), back_inserter(points),
          [](const v1d& v) { return v.front(); });

        for(v1d& vertice : subset)
            for_each(begin(vertice) + 1, end(vertice),
                [&points, &vertice, index = 1](int& x) mutable
                {
                    if (x == 1 && find(begin(points), end(points), index) == end(points))
                        vertice[index] = 0;
                    index++;
                });
    }
}

v3d modifyEdge(int l, int r, const v2d& graph_, int OP) // Add or remove edges
{
    v1d points;
    v2d pairs, temp;
    v3d ans, subsets;
    int degree = countDegree(graph_);
    auto tot = graph_.size() * (graph_.size() - 1);

    if(OP == 0) // delete edges
    {
        if (degree == 0 || 2 * l > degree)
            return {};
        if (2 * r > degree)
            r = degree / 2 + 1;
    }
    else // add edges
    {
        if (2 * l + degree > tot)
            return {};
        if (2 * (r - 1) + degree > tot)
            r = (tot - degree) / 2 + 1;
    }

    OP = OP == 0 ? 1 : 0; // reverse OP

    transform(begin(graph_), end(graph_), back_inserter(points),
      [](const v1d& v) { return v.front(); });

    for (auto i = 0; i < graph_.size(); i++)
    {
        for (auto j = 1; j < graph_[i].size(); j++)
        {
            if (
                graph_[i][j] == OP &&
                j != graph_[i][0] &&
                find(begin(points), end(points), j) != end(points)
                )
            {
                if (graph_[i][0] < j)
                {
                    pairs.emplace_back(initializer_list<int>{i, j});
                }
                else
                {
                    auto index_ =
                        find_if(begin(pairs), end(pairs),
                              [&](v1d pair)
                              {
                                  return graph_[pair[0]][0] == j && pair[1] == graph_[i][0];
                              })
                        - begin(pairs);

                    auto& temp = pairs[index_];
                    temp.push_back(i);
                    temp.push_back(j);
                }
            }
        }
    }

    generateSubsets(0, l, r, temp, subsets, pairs);

    OP = OP == 0 ? 1 : 0;

    transform(begin(subsets), end(subsets), back_inserter(ans),
        [&graph_, OP](v2d subset){
            v2d temp = graph_;
            for_each(begin(subset), end(subset),
                [&temp, OP](v1d pair)
                {
                    temp[pair[0]][pair[1]] = OP;
                    temp[pair[2]][pair[3]] = OP;
                });
            return temp;
        }
    );

    return ans;
}




v3d makeSubGraphs(v3d&& subsets)
{
    v3d subGraphs;

    for_each(begin(subsets), end(subsets),
        [&](v2d& subset)
        {
            if (subset.size() != 0)
            {
                auto temp = modifyEdge(0, 1e5, subset, DELETE);
                subGraphs.insert(end(subGraphs), begin(temp), end(temp));
            }
        });

    return subGraphs;
}

v3d addEdges(v3d&& subsets, int n)
{
    v3d subGraphs;

    for_each(begin(subsets), end(subsets),
        [&](v2d& subset)
        {
            if (!subset.empty())
            {
                auto degree = countDegree(subset);
                auto tot = (subset.size() - 1) *  (subset.size());
                int n_ = (tot - degree) / 2 >= n ? n : (tot-degree) / 2;
                auto temp = modifyEdge(n_, n_ + 1, subset, ADD);

                subGraphs.insert(end(subGraphs), begin(temp), end(temp));
            }
        });

    return subGraphs;
}

void testVertice(const v1d& vertice)
{
    for (auto x : vertice)
        cout << x << " ";
    cout << "\n";
}

void testSubsets(const v3d& subsets)
{
    for (auto x : subsets)
    {
        for (auto y : x)
        {
            for (auto z : y)
            {
                cout << z << " ";
            }
            cout << "\n";
        }
        cout << "\n";
    }
}

void testSubset(const v2d& subset)
{
    for (auto x : subset)
    {
        for (auto y : x)
        {
            cout << y << " ";
        }
        cout << "\n";
    }
    cout << "\n";
}

int main()
{
    buildGraph();
    v3d subsets_Q1, subsets_Q2, subsets_Q3_AC, subsets_Q3_WA;
    v2d temp_Q1, temp_Q2, temp_Q3_AC, temp_Q3_WA;


    testSubsets(subsets_Q3_AC);
    generateSubsets(0, 1, 6, temp_Q1, subsets_Q1, graph);
    generateSubsets(0, 4, 5, temp_Q2, subsets_Q2, graph);
    generateSubsets(0, 4, 5, temp_Q3_WA, subsets_Q3_WA, graph);
    repairSubsets(subsets_Q1);
    repairSubsets(subsets_Q2);
    repairSubsets(subsets_Q3_WA);

    auto subGraphs_Q1 = makeSubGraphs(move(subsets_Q1));
    auto subGraphs_Q2 = makeSubGraphs(move(subsets_Q2));
    auto modifiedSubsets_Q3_WA = addEdges(move(subsets_Q3_WA), 2);
    auto subGraphs_Q3_WA = makeSubGraphs(move(modifiedSubsets_Q3_WA));
    auto countGraphs =
        [](int n)
            {
                return
                    [&, n](v3d& subGraphs)
                    {
                        return
                            count_if(begin(subGraphs), end(subGraphs),
                                [&](v2d& subGraph)
                                {
                                    return
                                        find_if_not(begin(subGraph), end(subGraph),
                                            [&](v1d& vertice)
                                            {
                                                return
                                                    count(begin(vertice) + 1, end(vertice), 1) == n;
                                            } )
                                        ==
                                        end(subGraph);
                                });
                    };
            };

    /**************** Q3 *******************/
    subsets_Q3_AC = modifyEdge(2, 3, graph, ADD);
    v1d choices_Q3_AC;
    transform(begin(subsets_Q3_AC), end(subsets_Q3_AC), back_inserter(choices_Q3_AC),
                    [&](v2d graph_)
                    {
                        v2d temp_;
                        v3d subsets_;
                        generateSubsets(0, 1, 5, temp_, subsets_, graph_);
                        repairSubsets(subsets_);
                        auto subGraphs = makeSubGraphs(move(subsets_));
                        return countGraphs(3)(subGraphs);
                    });
    /*************************************/

    auto ans_Q1 = countGraphs(2)(subGraphs_Q1);
    auto ans_Q2 = countGraphs(3)(subGraphs_Q2);
    auto ans_Q3_WA = countGraphs(3)(subGraphs_Q3_WA);
    cout << "solution to Q1: " << ans_Q1 << "\n";
    cout << "solution to Q2: " << ans_Q2 << "\n";
    cout << "solution to Q3(all cases && WA): " << ans_Q3_WA << "\n";
    cout << "solution to Q3(maximum && AC): " << *max_element(begin(choices_Q3_AC), end(choices_Q3_AC));
    return 0;
}

Выход:

  • Решение 1 квартале: 17
  • Решение В2: 1
  • Решение В3 (во всех случаях и ВД): 9
  • Решение В3 (максимальное и ac): 5

Код доступен здесь



134
3
задан 3 апреля 2018 в 09:04 Источник Поделиться
Комментарии