#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;
}
