Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <algorithm>
- #include <iostream>
- #include <cstdio>
- #include <vector>
- #include <set>
- #include <cassert>
- #include <unordered_set>
- #include <random>
- using namespace std;
- vector<vector<int>> gr;
- mt19937 rr(random_device{}());
- int main() {
- /*ios_base::sync_with_stdio(false);
- cin.tie(NULL);
- cout.tie(NULL);*/
- freopen("input.txt", "r", stdin);
- // freopen("output.txt", "w", stdout);
- int n, m;
- cin >> n >> m;
- gr.resize(n);
- for (int i = 0; i < n; ++i) {
- int a, b;
- cin >> a >> b;
- --a;
- --b;
- gr[a].push_back(b);
- gr[b].push_back(a);
- }
- vector<int> v(n);
- vector<int> mx(n);
- int ans = 0;
- for (int i = 0; i < n; ++i)
- v[i] = i;
- for (int i = 0; i < 1e5; ++i) {
- shuffle(v.begin(), v.end(), rr);
- for (int cnt = n; cnt > 0; --cnt) {
- unordered_set<int> e;
- if (cnt <= ans)
- continue;
- for (int j = 0; j < cnt; ++j)
- e.insert(v[j]);
- bool fl = true;
- for (int j = 0; j < cnt; ++j) {
- int cnt1 = 0;
- for (auto x : gr[v[j]]) {
- if (e.find(x) != e.end())
- ++cnt1;
- }
- if (cnt1 < cnt/2) {
- fl = false;
- break;
- }
- }
- if (fl && cnt > ans) {
- ans = cnt;
- mx = v;
- }
- }
- }
- cout << ans << "\n";
- for (int i = 0; i < ans; ++i)
- cout << mx[i] + 1 << " ";
- cout << "\n";
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement