#include <cstdio> #include <cstdlib> #include <cstring> #include <string> #include <queue> #include <set> using namespace std; bool visited[200000 + 2]; set<int> G[200000 + 2]; int dfs(int v, bool print_vertices) { if (visited[v] || G[v].empty()) { return 0; } visited[v] = true; if (print_vertices) { printf("%d ", v); } int size = 1; for (set<int>::iterator it = G[v].begin(); it != G[v].end(); it++) { size += dfs(*it, print_vertices); } return size; } 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); G[a].insert(b); G[b].insert(a); } // // First phase: recursively reduce all vertices with less then d edges. // memset(visited, false, sizeof(visited)); queue<int> Q; for (int i = 1; i <= n; i++) { if (G[i].size() < d) { Q.push(i); visited[i] = true; } } while (!Q.empty()) { int v = Q.front(); Q.pop(); for (set<int>::iterator it = G[v].begin(); it != G[v].end(); it++) { int w = *it; G[w].erase(v); if (G[w].size() < d && !visited[w]) { Q.push(w); visited[w] = true; } } G[v].clear(); } // // Second phase: find the size of the largest subgraph and print it out. // memset(visited, false, sizeof(visited)); int max_v = 0; int max_size = 0; for (int i = 1; i <= n; i++) { int graph_size = dfs(i, false); if (max_size < graph_size) { max_v = i; max_size = graph_size; } } if (max_size == 0) { printf("NIE\n"); } else { printf("%d\n", max_size); memset(visited, false, sizeof(visited)); dfs(max_v, true); } 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 96 | #include <cstdio> #include <cstdlib> #include <cstring> #include <string> #include <queue> #include <set> using namespace std; bool visited[200000 + 2]; set<int> G[200000 + 2]; int dfs(int v, bool print_vertices) { if (visited[v] || G[v].empty()) { return 0; } visited[v] = true; if (print_vertices) { printf("%d ", v); } int size = 1; for (set<int>::iterator it = G[v].begin(); it != G[v].end(); it++) { size += dfs(*it, print_vertices); } return size; } 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); G[a].insert(b); G[b].insert(a); } // // First phase: recursively reduce all vertices with less then d edges. // memset(visited, false, sizeof(visited)); queue<int> Q; for (int i = 1; i <= n; i++) { if (G[i].size() < d) { Q.push(i); visited[i] = true; } } while (!Q.empty()) { int v = Q.front(); Q.pop(); for (set<int>::iterator it = G[v].begin(); it != G[v].end(); it++) { int w = *it; G[w].erase(v); if (G[w].size() < d && !visited[w]) { Q.push(w); visited[w] = true; } } G[v].clear(); } // // Second phase: find the size of the largest subgraph and print it out. // memset(visited, false, sizeof(visited)); int max_v = 0; int max_size = 0; for (int i = 1; i <= n; i++) { int graph_size = dfs(i, false); if (max_size < graph_size) { max_v = i; max_size = graph_size; } } if (max_size == 0) { printf("NIE\n"); } else { printf("%d\n", max_size); memset(visited, false, sizeof(visited)); dfs(max_v, true); } return 0; } |