#include <bits/stdc++.h> #define N 200001 bool visited[N]; int main() { int n, m, d, i, j, x, y, *p; scanf("%d%d%d", &n, &m, &d); std::list<int> graph[n+1]; for(i = 0; i < m; ++i) scanf("%d%d", &x, &y), graph[x].push_back(y), graph[y].push_back(x); std::stack<int> results; std::stack<std::list<int>::iterator> to_erase; std::stack<int> stack; for(i = 1; i <= n; ++i) { if(graph[i].size() >= d) { for(std::list<int>::iterator it = graph[i].begin(); it != graph[i].end(); ++it) if(graph[*it].size() < d) to_erase.push(it); while(!to_erase.empty()) graph[i].erase(to_erase.top()), to_erase.pop(); if(graph[i].size() >= d) results.push(i); } } int r = 0, index = 0; while(!results.empty()) { x = results.top(); if(!visited[x]) { j = 0; stack.push(x); while(!stack.empty()) { y = stack.top(); stack.pop(); if(!visited[y]) { visited[y] = true; for(std::list<int>::iterator it = graph[y].begin(); it != graph[y].end(); ++it) if(!visited[*it]) stack.push(*it); ++j; } } if(j > r) r = j, index = x; } results.pop(); } if(r) { for(i = 1; i <= N; ++i) visited[i] = false; stack.push(index); index = 0; int R[r]; while(!stack.empty()) { y = stack.top(); R[index] = y; ++index; stack.pop(); if(!visited[y]) { visited[y] = true; for(std::list<int>::iterator it = graph[y].begin(); it != graph[y].end(); ++it) if(!visited[*it]) stack.push(*it); } } std::sort(R, R+r); printf("%d\n", r); for(i = 0; i < r; ++i) printf("%d ", R[i]); } else puts("NIE"); }
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 | #include <bits/stdc++.h> #define N 200001 bool visited[N]; int main() { int n, m, d, i, j, x, y, *p; scanf("%d%d%d", &n, &m, &d); std::list<int> graph[n+1]; for(i = 0; i < m; ++i) scanf("%d%d", &x, &y), graph[x].push_back(y), graph[y].push_back(x); std::stack<int> results; std::stack<std::list<int>::iterator> to_erase; std::stack<int> stack; for(i = 1; i <= n; ++i) { if(graph[i].size() >= d) { for(std::list<int>::iterator it = graph[i].begin(); it != graph[i].end(); ++it) if(graph[*it].size() < d) to_erase.push(it); while(!to_erase.empty()) graph[i].erase(to_erase.top()), to_erase.pop(); if(graph[i].size() >= d) results.push(i); } } int r = 0, index = 0; while(!results.empty()) { x = results.top(); if(!visited[x]) { j = 0; stack.push(x); while(!stack.empty()) { y = stack.top(); stack.pop(); if(!visited[y]) { visited[y] = true; for(std::list<int>::iterator it = graph[y].begin(); it != graph[y].end(); ++it) if(!visited[*it]) stack.push(*it); ++j; } } if(j > r) r = j, index = x; } results.pop(); } if(r) { for(i = 1; i <= N; ++i) visited[i] = false; stack.push(index); index = 0; int R[r]; while(!stack.empty()) { y = stack.top(); R[index] = y; ++index; stack.pop(); if(!visited[y]) { visited[y] = true; for(std::list<int>::iterator it = graph[y].begin(); it != graph[y].end(); ++it) if(!visited[*it]) stack.push(*it); } } std::sort(R, R+r); printf("%d\n", r); for(i = 0; i < r; ++i) printf("%d ", R[i]); } else puts("NIE"); } |