#include <cstdio> #include <vector> #include <queue> #include <set> #include <map> using namespace std; int n, m, d; int a, b; vector<int> v[200000]; int deg[200000]; int t[200000]; int qu[200000]; struct cmp { bool operator() (const int &el1, const int &el2) { if(deg[el1] < deg[el2]) return true; else if(deg[el2] < deg[el1]) return false; return el1 < el2; } }; set<int, cmp> skm; // ~void wypisz() { // ~printf("SET:: "); // ~for(auto it = skm.begin(); it != skm.end(); ++it) { // ~printf("%d ", *it); // ~} // ~printf("\n"); // ~} set<int> bfs(int x) { int b, e; set<int> res; qu[b = e = 0] = x; t[x] = 1; while(b <= e) { x = qu[b++]; res.insert(x); for(int i = 0; i < v[x].size(); ++i) { if(t[v[x][i]] == 0 && skm.find(v[x][i]) != skm.end()) { t[v[x][i]] = t[x] + 1; qu[++e] = v[x][i]; } } } return res; } set<int> rozw() { set<int> res, tmp; for(int i = 0; i < n; ++i) { if(t[i] == 0 && skm.find(i) != skm.end()) { tmp = bfs(i); } if(res.size() < tmp.size()) res = tmp; } return res; } bool popraw() { //zwraca true jeżeli nie poprawił if(skm.empty() || deg[*(skm.begin())] >= d) return true; else { int w = *(skm.begin()); skm.erase(skm.begin()); for(int i = 0; i < v[w].size(); ++i) { int old = skm.size(); skm.erase(v[w][i]); deg[v[w][i]]--; if(old != skm.size()) skm.insert(v[w][i]); } } return false; } int main() { scanf("%d%d%d",&n, &m, &d); for(int i = 0; i < m; ++i) { scanf("%d%d", &a, &b); v[a-1].push_back(b-1); v[b-1].push_back(a-1); } for(int i = 0; i < n; ++i) { deg[i] = v[i].size(); } for(int i = 0; i < n; ++i) { skm.insert(i); } bool koniec = false; while(!koniec) { koniec = popraw(); } if(!skm.empty()) { set<int> res = rozw(); int size = res.size(); printf("%d\n", size); for(auto it= res.begin(); it != res.end(); ++it) { printf("%d ", (*it) + 1); } printf("\n"); } else { printf("NIE\n"); } 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 | #include <cstdio> #include <vector> #include <queue> #include <set> #include <map> using namespace std; int n, m, d; int a, b; vector<int> v[200000]; int deg[200000]; int t[200000]; int qu[200000]; struct cmp { bool operator() (const int &el1, const int &el2) { if(deg[el1] < deg[el2]) return true; else if(deg[el2] < deg[el1]) return false; return el1 < el2; } }; set<int, cmp> skm; // ~void wypisz() { // ~printf("SET:: "); // ~for(auto it = skm.begin(); it != skm.end(); ++it) { // ~printf("%d ", *it); // ~} // ~printf("\n"); // ~} set<int> bfs(int x) { int b, e; set<int> res; qu[b = e = 0] = x; t[x] = 1; while(b <= e) { x = qu[b++]; res.insert(x); for(int i = 0; i < v[x].size(); ++i) { if(t[v[x][i]] == 0 && skm.find(v[x][i]) != skm.end()) { t[v[x][i]] = t[x] + 1; qu[++e] = v[x][i]; } } } return res; } set<int> rozw() { set<int> res, tmp; for(int i = 0; i < n; ++i) { if(t[i] == 0 && skm.find(i) != skm.end()) { tmp = bfs(i); } if(res.size() < tmp.size()) res = tmp; } return res; } bool popraw() { //zwraca true jeżeli nie poprawił if(skm.empty() || deg[*(skm.begin())] >= d) return true; else { int w = *(skm.begin()); skm.erase(skm.begin()); for(int i = 0; i < v[w].size(); ++i) { int old = skm.size(); skm.erase(v[w][i]); deg[v[w][i]]--; if(old != skm.size()) skm.insert(v[w][i]); } } return false; } int main() { scanf("%d%d%d",&n, &m, &d); for(int i = 0; i < m; ++i) { scanf("%d%d", &a, &b); v[a-1].push_back(b-1); v[b-1].push_back(a-1); } for(int i = 0; i < n; ++i) { deg[i] = v[i].size(); } for(int i = 0; i < n; ++i) { skm.insert(i); } bool koniec = false; while(!koniec) { koniec = popraw(); } if(!skm.empty()) { set<int> res = rozw(); int size = res.size(); printf("%d\n", size); for(auto it= res.begin(); it != res.end(); ++it) { printf("%d ", (*it) + 1); } printf("\n"); } else { printf("NIE\n"); } return 0; } |