#include <cstdio> #include <vector> #include <utility> #include <set> #include <algorithm> using namespace std; const int GSIZE = 200007; const int DEAD = 0; typedef pair<int, int> pii; #define val first #define id second vector<int> graph[GSIZE]; int roads[GSIZE]; set<pii> order; pii countem(int sid, int father) { pii retval = make_pair(0, father); if(roads[sid] <= 0) return retval; ++retval.val; roads[sid] = -father; for(int i = 0; i < graph[sid].size(); ++i) retval.val += countem(graph[sid][i], father).val; return retval; } 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); graph[a].push_back(b); graph[b].push_back(a); roads[a]++; roads[b]++; } for(int i = 1; i <= n; ++i) order.insert(make_pair(roads[i], i)); while(!order.empty()) { pii top = *order.begin(); order.erase(top); if(top.val >= d) break; roads[top.id] = DEAD; for(int i = 0; i < graph[top.id].size(); ++i) { int other = graph[top.id][i]; if(roads[other] != DEAD) { order.erase(make_pair(roads[other], other)); --roads[other]; order.insert(make_pair(roads[other], other)); } } } pii res = make_pair(0, 0); for(int i = 1; i <= n; ++i) res = max(res, countem(i, i)); if(!res.val) { puts("NIE"); return 0; } printf("%d\n", res.val); for(int i = 1; i <= n; ++i) if(roads[i] == -res.id) printf("%d ", i); }
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 | #include <cstdio> #include <vector> #include <utility> #include <set> #include <algorithm> using namespace std; const int GSIZE = 200007; const int DEAD = 0; typedef pair<int, int> pii; #define val first #define id second vector<int> graph[GSIZE]; int roads[GSIZE]; set<pii> order; pii countem(int sid, int father) { pii retval = make_pair(0, father); if(roads[sid] <= 0) return retval; ++retval.val; roads[sid] = -father; for(int i = 0; i < graph[sid].size(); ++i) retval.val += countem(graph[sid][i], father).val; return retval; } 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); graph[a].push_back(b); graph[b].push_back(a); roads[a]++; roads[b]++; } for(int i = 1; i <= n; ++i) order.insert(make_pair(roads[i], i)); while(!order.empty()) { pii top = *order.begin(); order.erase(top); if(top.val >= d) break; roads[top.id] = DEAD; for(int i = 0; i < graph[top.id].size(); ++i) { int other = graph[top.id][i]; if(roads[other] != DEAD) { order.erase(make_pair(roads[other], other)); --roads[other]; order.insert(make_pair(roads[other], other)); } } } pii res = make_pair(0, 0); for(int i = 1; i <= n; ++i) res = max(res, countem(i, i)); if(!res.val) { puts("NIE"); return 0; } printf("%d\n", res.val); for(int i = 1; i <= n; ++i) if(roads[i] == -res.id) printf("%d ", i); } |