#include <cstdio> #include <map> #include <algorithm> #include <vector> #include <queue> using namespace std; typedef long long LL; typedef pair<LL,LL> PI; #define MP make_pair #define PB push_back #define SD second #define FT first int k,n,m,q,d; const int N = 200003; const int M = 200003; const LL INF = 2000000000000000000LL; int ilekraw[N]; bool duszek[N]; PI kraw[M]; int oj[N]; int ile[N]; int find(int a) { return oj[a] = oj[oj[a]] == oj[a] ? oj[a] : find(oj[a]); } void join(int a, int b) { a = find(a); b = find(b); if (a == b) return; if (ile[a] > ile[b]) swap(a, b); oj[b] = a; ile[a] += ile[b]; } deque<int> usuwanie; vector<int> sas[N]; int main() { scanf("%d%d%d",&n,&m,&d); for (int i = 0; i < m; i++) { int a, b; scanf("%d%d", &a, &b); a--; b--; kraw[i] = MP(a, b); ilekraw[a]++; ilekraw[b]++; sas[a].PB(b); sas[b].PB(a); } for (int i = 0; i < n; i++) { ile[i] = 1; oj[i] = i; if (ilekraw[i] < d) { duszek[i] = 1; usuwanie.PB(i); } } while (usuwanie.empty() == false) { int topa = usuwanie.back(); usuwanie.pop_back(); duszek[topa] = 1; for (int i = 0; i < sas[topa].size(); i++) { int v = sas[topa][i]; ilekraw[v]--; if (ilekraw[v] < d && duszek[v] == 0) { duszek[v] = 1; usuwanie.PB(v); } } } for (int i = 0; i < m; i++) { int a = kraw[i].FT; int b = kraw[i].SD; if (duszek[a] || duszek[b]) continue; join(a, b); } int res = 0; int max_id = -1; for (int i = 0; i < n; i++) if (duszek[i] == 0) { int tmp_id = find(i); if (res < ile[tmp_id]) { max_id = tmp_id; res = max(res, ile[tmp_id]); } } if (res < d) printf("NIE\n"); else { printf("%d\n", res); for (int i = 0; i < n; i++) if (find(i) == max_id) printf("%d ", i + 1); printf("\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 116 117 118 119 120 121 122 123 | #include <cstdio> #include <map> #include <algorithm> #include <vector> #include <queue> using namespace std; typedef long long LL; typedef pair<LL,LL> PI; #define MP make_pair #define PB push_back #define SD second #define FT first int k,n,m,q,d; const int N = 200003; const int M = 200003; const LL INF = 2000000000000000000LL; int ilekraw[N]; bool duszek[N]; PI kraw[M]; int oj[N]; int ile[N]; int find(int a) { return oj[a] = oj[oj[a]] == oj[a] ? oj[a] : find(oj[a]); } void join(int a, int b) { a = find(a); b = find(b); if (a == b) return; if (ile[a] > ile[b]) swap(a, b); oj[b] = a; ile[a] += ile[b]; } deque<int> usuwanie; vector<int> sas[N]; int main() { scanf("%d%d%d",&n,&m,&d); for (int i = 0; i < m; i++) { int a, b; scanf("%d%d", &a, &b); a--; b--; kraw[i] = MP(a, b); ilekraw[a]++; ilekraw[b]++; sas[a].PB(b); sas[b].PB(a); } for (int i = 0; i < n; i++) { ile[i] = 1; oj[i] = i; if (ilekraw[i] < d) { duszek[i] = 1; usuwanie.PB(i); } } while (usuwanie.empty() == false) { int topa = usuwanie.back(); usuwanie.pop_back(); duszek[topa] = 1; for (int i = 0; i < sas[topa].size(); i++) { int v = sas[topa][i]; ilekraw[v]--; if (ilekraw[v] < d && duszek[v] == 0) { duszek[v] = 1; usuwanie.PB(v); } } } for (int i = 0; i < m; i++) { int a = kraw[i].FT; int b = kraw[i].SD; if (duszek[a] || duszek[b]) continue; join(a, b); } int res = 0; int max_id = -1; for (int i = 0; i < n; i++) if (duszek[i] == 0) { int tmp_id = find(i); if (res < ile[tmp_id]) { max_id = tmp_id; res = max(res, ile[tmp_id]); } } if (res < d) printf("NIE\n"); else { printf("%d\n", res); for (int i = 0; i < n; i++) if (find(i) == max_id) printf("%d ", i + 1); printf("\n"); } return 0; } |