#include <cstdio> #include <set> #include <algorithm> using namespace std; struct Node{ int color; int nRoads; set<int> roads; Node() : nRoads(0), color(0) {} }; int n, m, d; Node *nodes; void remove(int num){ if(nodes[num].color < 0) return; nodes[num].color = -1; nodes[num].nRoads = 0; for(set<int>::iterator it = nodes[num].roads.begin(); it != nodes[num].roads.end(); it++){ nodes[*it].nRoads--; nodes[*it].roads.erase(num); if(nodes[*it].nRoads < d) remove(*it); } nodes[num].roads.clear(); } int paint(int num, int col){ if(nodes[num].color != 0) return 0; nodes[num].color = col; int painted = 1; for(set<int>::iterator it = nodes[num].roads.begin(); it != nodes[num].roads.end(); it++) painted += paint(*it, col); return painted; } int main(){ scanf("%d %d %d", &n, &m, &d); nodes = new Node[n+1]; for(int i=1; i<=n; i++){ nodes[i].nRoads = 0; nodes[i].color = 0; } for(int i=1; i<=m; i++){ int a, b; scanf("%d %d", &a, &b); nodes[a].roads.insert(b); nodes[b].roads.insert(a); nodes[a].nRoads++; nodes[b].nRoads++; } for(int i=1; i<=n; i++) if(nodes[i].nRoads < d) remove(i); int bestColor = 0; int bestColored = 0; for(int i=1; i<=n; i++){ int colored = paint(i, i); if(colored > bestColored){ bestColored = colored; bestColor = i; } } if(bestColored > 0){ printf("%d\n", bestColored); for(int i=1; i<=n; i++) if(nodes[i].color == bestColor) printf("%d ", i); }else{ printf("NIE\n"); } delete [] nodes; 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 | #include <cstdio> #include <set> #include <algorithm> using namespace std; struct Node{ int color; int nRoads; set<int> roads; Node() : nRoads(0), color(0) {} }; int n, m, d; Node *nodes; void remove(int num){ if(nodes[num].color < 0) return; nodes[num].color = -1; nodes[num].nRoads = 0; for(set<int>::iterator it = nodes[num].roads.begin(); it != nodes[num].roads.end(); it++){ nodes[*it].nRoads--; nodes[*it].roads.erase(num); if(nodes[*it].nRoads < d) remove(*it); } nodes[num].roads.clear(); } int paint(int num, int col){ if(nodes[num].color != 0) return 0; nodes[num].color = col; int painted = 1; for(set<int>::iterator it = nodes[num].roads.begin(); it != nodes[num].roads.end(); it++) painted += paint(*it, col); return painted; } int main(){ scanf("%d %d %d", &n, &m, &d); nodes = new Node[n+1]; for(int i=1; i<=n; i++){ nodes[i].nRoads = 0; nodes[i].color = 0; } for(int i=1; i<=m; i++){ int a, b; scanf("%d %d", &a, &b); nodes[a].roads.insert(b); nodes[b].roads.insert(a); nodes[a].nRoads++; nodes[b].nRoads++; } for(int i=1; i<=n; i++) if(nodes[i].nRoads < d) remove(i); int bestColor = 0; int bestColored = 0; for(int i=1; i<=n; i++){ int colored = paint(i, i); if(colored > bestColored){ bestColored = colored; bestColor = i; } } if(bestColored > 0){ printf("%d\n", bestColored); for(int i=1; i<=n; i++) if(nodes[i].color == bestColor) printf("%d ", i); }else{ printf("NIE\n"); } delete [] nodes; return 0; } |