이거 종만 아재가 완전탐색으로 풀라고 던진 문제임.
어차피 선택 문제이므로 노드를 탐색하는 순서가 하나면 됨.
예를들어서 연결된 노드의 숫자가 적은 노드부터, 혹은 많은 노드부터 순서대로 조사하는 거임.
상식적으로 적은 노드부터 하는게 더 빠를거라고 생각될 거임.
실제로 알고스팟 결과는 2배 정도 차이남.
#include <iostream>
#include <vector>
#include <algorithm>
//#include "Random.h" class Class
{
public:
Class() = default;
~Class() = default; friend std::istream& operator>>(std::istream& in, Class& rhs)
{
in >> rhs.nStudent >> rhs.nFriend; for (int i = 0; i < rhs.nFriend; i++)
{
std::pair<int, int> tmp;
in >> tmp.first >> tmp.second;
rhs.m_friends.emplace_back(tmp);
} return in;
} std::vector<int> Init_Code_Count(std::vector<std::pair<int, int>> friend_relations)
{
std::vector<int> code_count(nStudent); for (const auto& f : friend_relations)
{
code_count[f.first]++;
code_count[f.second]++;
} for (auto& c : code_count)
if (c <= 0)
c = 99999; return code_count;
} void Do()
{
std::cout << Delete_Til(std::make_pair(-1, -1), Init_Code_Count(m_friends), m_friends) << std::endl;;
} int Delete_Til(std::pair<int, int> choosen, std::vector<int> code_count, std::vector<std::pair<int, int>> friend_relations)
{
int result = 0; if (choosen.first != -1)
{
code_count[choosen.first] = 999999;
code_count[choosen.second] = 999999; for (auto iter = friend_relations.begin(); iter != friend_relations.end();)
{
if (iter->first == choosen.first || iter->second == choosen.first ||
iter->first == choosen.second || iter->second == choosen.second)
iter = friend_relations.erase(iter);
else
iter++;
}
} if (friend_relations.size() <= 0)
{
for (const auto& c : code_count)
{
if (c != 999999)
return 0;
}
return 1;
} auto _min = *std::min_element(code_count.begin(), code_count.end());
std::vector<int> _student_with_min_friends;
for (int i = 0; i < nStudent; i++)
if (code_count[i] == _min)
{
_student_with_min_friends.push_back(i);
break;
}
auto a = Find(_student_with_min_friends, friend_relations); for (auto s : Find(_student_with_min_friends, friend_relations))
{
result += Delete_Til(s, code_count, friend_relations);
} return result;
} std::vector<std::pair<int, int>> Find(std::vector<int>& student_with_min_friends, std::vector<std::pair<int, int>>& friend_relations)
{
std::vector<std::pair<int, int>> results; for (auto f : friend_relations)
{
bool isChoosen = false;
for (auto s : student_with_min_friends)
{
if ((f.first == s || f.second == s) && !isChoosen)
{
results.emplace_back(f);
isChoosen = true;
}
}
} return results;
} private:
int nStudent;
int nFriend;
std::vector<std::pair<int, int>> m_friends; }; int main()
{
int nCase;
std::vector<Class> classes;
std::cin >> nCase;
for (int i = 0; i < nCase; i++)
{
Class cls;
std::cin >> cls;
classes.emplace_back(cls);
}
for (auto cls : classes)
{
cls.Do();
}
}