#include <cstdio> #include <vector> #include <algorithm> using namespace std; int n, m, d; vector<int>* E; int* deg; bool* deleted; vector<int> dfsList; void DFS_Delete(int v) { deleted[v] = true; for (int i = 0; i < E[v].size(); i++) if (!deleted[E[v][i]]) { deg[E[v][i]]--; if (deg[E[v][i]] < d) DFS_Delete(E[v][i]); } } int DFS_Count(int v) { deleted[v] = true; dfsList.push_back(v); int count = 1; for (int i = 0; i < E[v].size(); i++) if (!deleted[E[v][i]]) count += DFS_Count(E[v][i]); return count; } int main() { scanf("%d %d %d", &n, &m, &d); E = new vector<int>[n]; deg = new int[n]; deleted = new bool[n]; for (int i = 0; i < n; i++) { deg[i] = 0; deleted[i] = false; } for (int i = 0; i < m; i++) { int a, b; scanf("%d %d", &a, &b); E[a-1].push_back(b-1); E[b-1].push_back(a-1); deg[a-1]++; deg[b-1]++; } for (int i = 0; i < n; i++) if (!deleted[i] && deg[i] < d) DFS_Delete(i); int best = 0, bestStart, bestEnd; for (int i = 0; i < n; i++) if (!deleted[i]) { int start = dfsList.size(); int c = DFS_Count(i); if (c > best) { best = c; bestStart = start; bestEnd = dfsList.size(); } } if (best > 0) { printf("%d\n", best); sort(dfsList.begin()+bestStart, dfsList.begin()+bestEnd); for (int i = bestStart; i < bestEnd-1; i++) printf("%d ", dfsList[i]+1); printf("%d\n", dfsList[bestEnd-1]+1); } else printf("NIE\n"); // system("pause"); 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 | #include <cstdio> #include <vector> #include <algorithm> using namespace std; int n, m, d; vector<int>* E; int* deg; bool* deleted; vector<int> dfsList; void DFS_Delete(int v) { deleted[v] = true; for (int i = 0; i < E[v].size(); i++) if (!deleted[E[v][i]]) { deg[E[v][i]]--; if (deg[E[v][i]] < d) DFS_Delete(E[v][i]); } } int DFS_Count(int v) { deleted[v] = true; dfsList.push_back(v); int count = 1; for (int i = 0; i < E[v].size(); i++) if (!deleted[E[v][i]]) count += DFS_Count(E[v][i]); return count; } int main() { scanf("%d %d %d", &n, &m, &d); E = new vector<int>[n]; deg = new int[n]; deleted = new bool[n]; for (int i = 0; i < n; i++) { deg[i] = 0; deleted[i] = false; } for (int i = 0; i < m; i++) { int a, b; scanf("%d %d", &a, &b); E[a-1].push_back(b-1); E[b-1].push_back(a-1); deg[a-1]++; deg[b-1]++; } for (int i = 0; i < n; i++) if (!deleted[i] && deg[i] < d) DFS_Delete(i); int best = 0, bestStart, bestEnd; for (int i = 0; i < n; i++) if (!deleted[i]) { int start = dfsList.size(); int c = DFS_Count(i); if (c > best) { best = c; bestStart = start; bestEnd = dfsList.size(); } } if (best > 0) { printf("%d\n", best); sort(dfsList.begin()+bestStart, dfsList.begin()+bestEnd); for (int i = bestStart; i < bestEnd-1; i++) printf("%d ", dfsList[i]+1); printf("%d\n", dfsList[bestEnd-1]+1); } else printf("NIE\n"); // system("pause"); return 0; } |