/* Mistrzostwa [B] * Marek Iwaniuk * O(n) */ //#include "stdafx.h" #include <iostream> #include <cstdio> #include <queue> //#define scanf scanf_s #define INF 999999999 #define MAX_T 200100 using namespace std; class Cities { private: int n, m, from, to, k, max_res = 0, res = 0, beg = 0; int DelCount[MAX_T]; bool Delete[MAX_T]; bool Visited[MAX_T]; queue<pair<int, int> > Heap; vector<int> Coincidence[MAX_T]; public: Cities() { scanf("%d %d %d", &n, &m, &k); for (int i = 0; i < m; i++) { scanf("%d %d", &from, &to); Coincidence[from].push_back(to); Coincidence[to].push_back(from); } for (int i = 1; i <= n; i++) { Delete[i] = Visited[i] = false; DelCount[i] = 0; if (Coincidence[i].size() < k) { Heap.push(make_pair(Coincidence[i].size(), i)); Delete[i] = true; } } } void DeleteUnuseful() { while (Heap.size() > 0) { pair<int, int> Top = Heap.front(); Heap.pop(); Top.first -= DelCount[Top.second]; DelCount[Top.second] = INF; for (int i = 0; i < Coincidence[Top.second].size(); i++) { int frnd = Coincidence[Top.second][i]; DelCount[frnd]++; if (Coincidence[frnd].size() - DelCount[frnd] < k && Delete[frnd] == false) { Heap.push(make_pair(Coincidence[frnd].size(), Coincidence[Top.second][i])); Delete[frnd] = true; } } } } int BFS(int from) { int res = 1; queue<int> Heap; Heap.push(from); Visited[from] = true; DelCount[from] = from; while (!Heap.empty()) { int top = Heap.front(); Heap.pop(); int frnd_count = 0; for (int i = 0; i < Coincidence[top].size(); i++) { int frnd = Coincidence[top][i]; frnd_count++; if (!Visited[frnd] && !Delete[frnd]) { Heap.push(frnd); Visited[frnd] = true; DelCount[frnd] = from; res++; } } } return res; } void BFS() { beg = 0; for (int i = 1; i <= n; i++) { if (!Delete[i] && !Visited[i]) { res = BFS(i); if (res >= max_res) { max_res = res; beg = i; } } } } void Answer() { if (max_res == 0) { printf("NIE"); } else { printf("%d\n", max_res); for (int i = 1; i <= n; i++) { if (DelCount[i] == beg) { printf("%d ", i); } } } } }; int main() { Cities *New = new Cities(); New->DeleteUnuseful(); New->BFS(); New->Answer(); return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 | /* Mistrzostwa [B] * Marek Iwaniuk * O(n) */ //#include "stdafx.h" #include <iostream> #include <cstdio> #include <queue> //#define scanf scanf_s #define INF 999999999 #define MAX_T 200100 using namespace std; class Cities { private: int n, m, from, to, k, max_res = 0, res = 0, beg = 0; int DelCount[MAX_T]; bool Delete[MAX_T]; bool Visited[MAX_T]; queue<pair<int, int> > Heap; vector<int> Coincidence[MAX_T]; public: Cities() { scanf("%d %d %d", &n, &m, &k); for (int i = 0; i < m; i++) { scanf("%d %d", &from, &to); Coincidence[from].push_back(to); Coincidence[to].push_back(from); } for (int i = 1; i <= n; i++) { Delete[i] = Visited[i] = false; DelCount[i] = 0; if (Coincidence[i].size() < k) { Heap.push(make_pair(Coincidence[i].size(), i)); Delete[i] = true; } } } void DeleteUnuseful() { while (Heap.size() > 0) { pair<int, int> Top = Heap.front(); Heap.pop(); Top.first -= DelCount[Top.second]; DelCount[Top.second] = INF; for (int i = 0; i < Coincidence[Top.second].size(); i++) { int frnd = Coincidence[Top.second][i]; DelCount[frnd]++; if (Coincidence[frnd].size() - DelCount[frnd] < k && Delete[frnd] == false) { Heap.push(make_pair(Coincidence[frnd].size(), Coincidence[Top.second][i])); Delete[frnd] = true; } } } } int BFS(int from) { int res = 1; queue<int> Heap; Heap.push(from); Visited[from] = true; DelCount[from] = from; while (!Heap.empty()) { int top = Heap.front(); Heap.pop(); int frnd_count = 0; for (int i = 0; i < Coincidence[top].size(); i++) { int frnd = Coincidence[top][i]; frnd_count++; if (!Visited[frnd] && !Delete[frnd]) { Heap.push(frnd); Visited[frnd] = true; DelCount[frnd] = from; res++; } } } return res; } void BFS() { beg = 0; for (int i = 1; i <= n; i++) { if (!Delete[i] && !Visited[i]) { res = BFS(i); if (res >= max_res) { max_res = res; beg = i; } } } } void Answer() { if (max_res == 0) { printf("NIE"); } else { printf("%d\n", max_res); for (int i = 1; i <= n; i++) { if (DelCount[i] == beg) { printf("%d ", i); } } } } }; int main() { Cities *New = new Cities(); New->DeleteUnuseful(); New->BFS(); New->Answer(); return 0; } |