#include<cstdio> #include<set> #include<vector> #include<algorithm> #include<string.h> #include<map> #include<iostream> using namespace std; #define MAX_N 200000 vector<int> graph[MAX_N + 1]; int n, m, d; bool deleted[MAX_N + 1]; bool visited[MAX_N + 1]; int removedEdges[MAX_N + 1]; vector<int> component; void go(int v) { deleted[v] = true; for (int i = 0; i < graph[v].size(); i++) { removedEdges[graph[v][i]]++; if (graph[graph[v][i]].size() - removedEdges[graph[v][i]] < d && !deleted[graph[v][i]]) { go(graph[v][i]); } } } void getComponent(int v) { visited[v] = true; component.push_back(v); for (int i = 0; i < graph[v].size(); i++) { if (!visited[graph[v][i]] && !deleted[graph[v][i]]) { getComponent(graph[v][i]); } } } int main() { cin >> n >> m >> d; for (int i = 0; i < m; i++) { int a, b; cin >> a >> b; graph[a].push_back(b); graph[b].push_back(a); } for (int i = 1; i <= n; i++) { if (graph[i].size() < d && !deleted[i]) { go(i); } } vector<int> best; for (int i = 1; i <= n; i++) { if(!deleted[i] && !visited[i]) { component.clear(); getComponent(i); if (component.size() > best.size()) { best = component; } } } if (best.size()) { sort(best.begin(), best.end()); cout << best.size() << "\n"; for (int i = 0; i < best.size(); i++) { cout << best[i] << " "; } } else { cout << "NIE\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 | #include<cstdio> #include<set> #include<vector> #include<algorithm> #include<string.h> #include<map> #include<iostream> using namespace std; #define MAX_N 200000 vector<int> graph[MAX_N + 1]; int n, m, d; bool deleted[MAX_N + 1]; bool visited[MAX_N + 1]; int removedEdges[MAX_N + 1]; vector<int> component; void go(int v) { deleted[v] = true; for (int i = 0; i < graph[v].size(); i++) { removedEdges[graph[v][i]]++; if (graph[graph[v][i]].size() - removedEdges[graph[v][i]] < d && !deleted[graph[v][i]]) { go(graph[v][i]); } } } void getComponent(int v) { visited[v] = true; component.push_back(v); for (int i = 0; i < graph[v].size(); i++) { if (!visited[graph[v][i]] && !deleted[graph[v][i]]) { getComponent(graph[v][i]); } } } int main() { cin >> n >> m >> d; for (int i = 0; i < m; i++) { int a, b; cin >> a >> b; graph[a].push_back(b); graph[b].push_back(a); } for (int i = 1; i <= n; i++) { if (graph[i].size() < d && !deleted[i]) { go(i); } } vector<int> best; for (int i = 1; i <= n; i++) { if(!deleted[i] && !visited[i]) { component.clear(); getComponent(i); if (component.size() > best.size()) { best = component; } } } if (best.size()) { sort(best.begin(), best.end()); cout << best.size() << "\n"; for (int i = 0; i < best.size(); i++) { cout << best[i] << " "; } } else { cout << "NIE\n"; } return 0; } |