#include <cstdio> #include <algorithm> #include <vector> #define FOR(x, n) for(int x = 0, __n = (n); x < __n; x++) #define FORI(x, a, n) for(int x = (a), __n = (n); x < __n; x++) #define FORR(x, n) for(int x = (n)-1; x >= 0; x--) using namespace std; #define MAXN 100001 #define var long long struct node { bool rem; vector<int> L; int total; node():rem(false), total(0), root(NULL), weight(1){} void addConnection(int p) { L.push_back(p); total++; } int reduce() { return --total; } node* root; int weight; node* getRoot() { if(root) return root = root->getRoot(); return this; } void join(node* o) { if(root) { getRoot()->join(o); return; } o = o->getRoot(); if(o == this) return; if(o->weight > weight) o->join(this); o->root = this; weight += o->weight; } } t[MAXN]; main() { int n,m,d; scanf("%d%d%d", &n, &m, &d); FOR(i, m) { int a, b; scanf("%d%d", &a, &b); a--, b--; t[a].addConnection(b); t[b].addConnection(a); } vector<int> S; FOR(i,n) { if(t[i].total < d) { S.push_back(i); t[i].rem = true; } } while(!S.empty()){ int v = S.back(); S.pop_back(); FOR(i, t[v].L.size()) { int j = t[v].L[i]; if(t[j].rem) continue; if(t[j].reduce() < d) { t[j].rem = true; S.push_back(j); } } } FOR(i, n) { if(t[i].rem) continue; FOR(k, t[i].L.size()) { int j = t[i].L[k]; if(t[j].rem) continue; t[i].join(&t[j]); } } int res = 0; node* best = NULL; FOR(i, n) { if(!t[i].rem && t[i].weight > res) { res = t[i].weight; best = &t[i]; } } if(res > 0) { printf("%d\n", res); FOR(i, n) { if(t[i].getRoot() == best) { printf("%d ", i+1); } } printf("\n"); } else { printf("NIE\n"); } }
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 | #include <cstdio> #include <algorithm> #include <vector> #define FOR(x, n) for(int x = 0, __n = (n); x < __n; x++) #define FORI(x, a, n) for(int x = (a), __n = (n); x < __n; x++) #define FORR(x, n) for(int x = (n)-1; x >= 0; x--) using namespace std; #define MAXN 100001 #define var long long struct node { bool rem; vector<int> L; int total; node():rem(false), total(0), root(NULL), weight(1){} void addConnection(int p) { L.push_back(p); total++; } int reduce() { return --total; } node* root; int weight; node* getRoot() { if(root) return root = root->getRoot(); return this; } void join(node* o) { if(root) { getRoot()->join(o); return; } o = o->getRoot(); if(o == this) return; if(o->weight > weight) o->join(this); o->root = this; weight += o->weight; } } t[MAXN]; main() { int n,m,d; scanf("%d%d%d", &n, &m, &d); FOR(i, m) { int a, b; scanf("%d%d", &a, &b); a--, b--; t[a].addConnection(b); t[b].addConnection(a); } vector<int> S; FOR(i,n) { if(t[i].total < d) { S.push_back(i); t[i].rem = true; } } while(!S.empty()){ int v = S.back(); S.pop_back(); FOR(i, t[v].L.size()) { int j = t[v].L[i]; if(t[j].rem) continue; if(t[j].reduce() < d) { t[j].rem = true; S.push_back(j); } } } FOR(i, n) { if(t[i].rem) continue; FOR(k, t[i].L.size()) { int j = t[i].L[k]; if(t[j].rem) continue; t[i].join(&t[j]); } } int res = 0; node* best = NULL; FOR(i, n) { if(!t[i].rem && t[i].weight > res) { res = t[i].weight; best = &t[i]; } } if(res > 0) { printf("%d\n", res); FOR(i, n) { if(t[i].getRoot() == best) { printf("%d ", i+1); } } printf("\n"); } else { printf("NIE\n"); } } |