#include <cstdio> #include <vector> #include <queue> using namespace std; struct wp{ vector<int> v; }; wp t[200005]; wp t2[200005]; int zlicz[200005]; queue<int> q; int odw[200005]; int licz[200005]; pair<int,int> pol[200005]; bool odww[200005]; int main(){ int n,m,d; scanf("%d%d%d", &n,&m,&d); for (int i = 0; i < m; i++){ int a,b; scanf("%d%d", &a,&b); t[a].v.push_back(b); t[b].v.push_back(a); pol[i] = make_pair(a,b); } for (int i = 1; i <= n; i++){ zlicz[i] = t[i].v.size(); if (zlicz[i] < d){ q.push(i); // zlicz[i] = 0; odww[i] = 1; // printf("%d ", i); } //printf("%d ", zlicz[i]); } while(!q.empty()){ int v1 = q.front(); q.pop(); zlicz[v1] = 0; for(vector<int>::iterator it = t[v1].v.begin(); it != t[v1].v.end(); it++){ if (odww[*it] == 0){ zlicz[*it]--; if (zlicz[*it] < d){ odww[*it] = 1; // zlicz[*it] = 0; q.push(*it); //printf("%d\n", *it); } } } } for (int i = 0; i < m; i++){ int a = pol[i].first; int b = pol[i].second; if (zlicz[a] >= d && zlicz[b] >= d){ t2[a].v.push_back(b); t2[b].v.push_back(a); } } /* for (int i = 1; i <= n; i++){ printf("%d: ", i); for (vector<int>::iterator it = t2[i].v.begin(); it != t2[i].v.end(); it++) printf("%d ", *it); printf("\n"); }*/ for (int i = 1; i <= n; i++) odw[i] = -1; for (int i = 1; i <= n; i++){ if(zlicz[i] >= d && odw[i] == -1){ odw[i] = i; q.push(i); while(!q.empty()){ int v1 = q.front(); q.pop(); for (vector<int>::iterator it = t2[v1].v.begin(); it != t2[v1].v.end(); it++){ if (odw[*it] == -1){ odw[*it] = i; q.push(*it); } } } } } for (int i = 1; i <= n; i++){ //printf("%d ", odw[i]); if (odw[i] != -1) licz[odw[i]]++; } int besti = 0; int maks = 0; for (int i = 1; i <= n; i++){ //printf("%d ", licz[odw[i]]); if (maks < licz[i]){ maks = licz[i]; besti = i; } } //printf("%d %d\n", maks,besti); if (maks < d){ printf("NIE"); return 0; } printf("%d\n", maks); for (int i = 1; i <= n; i++){ if (odw[i] == besti) printf("%d ", i); } }
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 | #include <cstdio> #include <vector> #include <queue> using namespace std; struct wp{ vector<int> v; }; wp t[200005]; wp t2[200005]; int zlicz[200005]; queue<int> q; int odw[200005]; int licz[200005]; pair<int,int> pol[200005]; bool odww[200005]; int main(){ int n,m,d; scanf("%d%d%d", &n,&m,&d); for (int i = 0; i < m; i++){ int a,b; scanf("%d%d", &a,&b); t[a].v.push_back(b); t[b].v.push_back(a); pol[i] = make_pair(a,b); } for (int i = 1; i <= n; i++){ zlicz[i] = t[i].v.size(); if (zlicz[i] < d){ q.push(i); // zlicz[i] = 0; odww[i] = 1; // printf("%d ", i); } //printf("%d ", zlicz[i]); } while(!q.empty()){ int v1 = q.front(); q.pop(); zlicz[v1] = 0; for(vector<int>::iterator it = t[v1].v.begin(); it != t[v1].v.end(); it++){ if (odww[*it] == 0){ zlicz[*it]--; if (zlicz[*it] < d){ odww[*it] = 1; // zlicz[*it] = 0; q.push(*it); //printf("%d\n", *it); } } } } for (int i = 0; i < m; i++){ int a = pol[i].first; int b = pol[i].second; if (zlicz[a] >= d && zlicz[b] >= d){ t2[a].v.push_back(b); t2[b].v.push_back(a); } } /* for (int i = 1; i <= n; i++){ printf("%d: ", i); for (vector<int>::iterator it = t2[i].v.begin(); it != t2[i].v.end(); it++) printf("%d ", *it); printf("\n"); }*/ for (int i = 1; i <= n; i++) odw[i] = -1; for (int i = 1; i <= n; i++){ if(zlicz[i] >= d && odw[i] == -1){ odw[i] = i; q.push(i); while(!q.empty()){ int v1 = q.front(); q.pop(); for (vector<int>::iterator it = t2[v1].v.begin(); it != t2[v1].v.end(); it++){ if (odw[*it] == -1){ odw[*it] = i; q.push(*it); } } } } } for (int i = 1; i <= n; i++){ //printf("%d ", odw[i]); if (odw[i] != -1) licz[odw[i]]++; } int besti = 0; int maks = 0; for (int i = 1; i <= n; i++){ //printf("%d ", licz[odw[i]]); if (maks < licz[i]){ maks = licz[i]; besti = i; } } //printf("%d %d\n", maks,besti); if (maks < d){ printf("NIE"); return 0; } printf("%d\n", maks); for (int i = 1; i <= n; i++){ if (odw[i] == besti) printf("%d ", i); } } |