#include <cstdio> #include <vector> #include <set> #include <algorithm> #include <queue> #include <string.h> using namespace std; struct Node { int id; int connectionsCount; bool operator()(const Node *lhs, const Node *rhs) const { if (lhs->connectionsCount != rhs->connectionsCount) return lhs->connectionsCount < rhs->connectionsCount; return lhs->id < rhs->id; } }; int bfs(const vector<int> graph[], bool alive[], int colors[], int start, int color); int main() { int n, m, d; scanf("%d%d%d", &n, &m, &d); vector<int> graph[n]; bool alive[n]; memset(alive, 0, sizeof(alive)); Node *nodesT[n]; for (int i = 0; i < m; i++) { int a, b; scanf("%d%d", &a, &b); graph[a - 1].push_back(b - 1); graph[b - 1].push_back(a - 1); } set<Node *, Node> nodesS; for (int i = 0; i < n; i++) { nodesT[i] = new Node(); nodesT[i]->id = i; nodesT[i]->connectionsCount = (int) graph[i].size(); if (nodesT[i]->connectionsCount > 0) alive[i] = true; nodesS.insert(nodesT[i]); } while (!nodesS.empty()) { Node *first = *nodesS.begin(); if (first->connectionsCount >= d) break; nodesS.erase(first); alive[first->id] = false; for (int i = 0; i < graph[first->id].size(); i++) { int target = graph[first->id][i]; Node *node = nodesT[target]; if (alive[node->id]) { Node *reference = *nodesS.find(node); nodesS.erase(reference); node->connectionsCount--; nodesS.insert(node); } } } int colors[n]; memset(colors, 0, sizeof(colors)); int currentColor = 1; int bestColor = 0; int bestCount = 0; for (int i = 0; i < n; i++) { if (alive[i]) { int count = bfs(graph, alive, colors, i, currentColor); if (bestCount < count) { bestColor = currentColor; bestCount = count; } currentColor++; } } if (bestColor == 0) { printf("NIE\n"); return 0; } printf("%d\n", bestCount); for (int i = 0; i < n; i++) if (colors[i] == bestColor) printf("%d ", i + 1); printf("\n"); return 0; } int bfs(const vector<int> graph[], bool alive[], int colors[], int start, int color) { int count = 0; queue<int> Q; Q.push(start); while (!Q.empty()) { int id = Q.front(); Q.pop(); count++; colors[id] = color; alive[id] = false; for (int i = 0; i < graph[id].size(); i++) { int target = graph[id][i]; if (alive[target]) { Q.push(target); alive[target] = false; } } } return count; }
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 | #include <cstdio> #include <vector> #include <set> #include <algorithm> #include <queue> #include <string.h> using namespace std; struct Node { int id; int connectionsCount; bool operator()(const Node *lhs, const Node *rhs) const { if (lhs->connectionsCount != rhs->connectionsCount) return lhs->connectionsCount < rhs->connectionsCount; return lhs->id < rhs->id; } }; int bfs(const vector<int> graph[], bool alive[], int colors[], int start, int color); int main() { int n, m, d; scanf("%d%d%d", &n, &m, &d); vector<int> graph[n]; bool alive[n]; memset(alive, 0, sizeof(alive)); Node *nodesT[n]; for (int i = 0; i < m; i++) { int a, b; scanf("%d%d", &a, &b); graph[a - 1].push_back(b - 1); graph[b - 1].push_back(a - 1); } set<Node *, Node> nodesS; for (int i = 0; i < n; i++) { nodesT[i] = new Node(); nodesT[i]->id = i; nodesT[i]->connectionsCount = (int) graph[i].size(); if (nodesT[i]->connectionsCount > 0) alive[i] = true; nodesS.insert(nodesT[i]); } while (!nodesS.empty()) { Node *first = *nodesS.begin(); if (first->connectionsCount >= d) break; nodesS.erase(first); alive[first->id] = false; for (int i = 0; i < graph[first->id].size(); i++) { int target = graph[first->id][i]; Node *node = nodesT[target]; if (alive[node->id]) { Node *reference = *nodesS.find(node); nodesS.erase(reference); node->connectionsCount--; nodesS.insert(node); } } } int colors[n]; memset(colors, 0, sizeof(colors)); int currentColor = 1; int bestColor = 0; int bestCount = 0; for (int i = 0; i < n; i++) { if (alive[i]) { int count = bfs(graph, alive, colors, i, currentColor); if (bestCount < count) { bestColor = currentColor; bestCount = count; } currentColor++; } } if (bestColor == 0) { printf("NIE\n"); return 0; } printf("%d\n", bestCount); for (int i = 0; i < n; i++) if (colors[i] == bestColor) printf("%d ", i + 1); printf("\n"); return 0; } int bfs(const vector<int> graph[], bool alive[], int colors[], int start, int color) { int count = 0; queue<int> Q; Q.push(start); while (!Q.empty()) { int id = Q.front(); Q.pop(); count++; colors[id] = color; alive[id] = false; for (int i = 0; i < graph[id].size(); i++) { int target = graph[id][i]; if (alive[target]) { Q.push(target); alive[target] = false; } } } return count; } |