#include <iostream> #include <cstdio> #include <ctime> #include <cstdlib> #include <algorithm> #include <cmath> #include <vector> #include <map> #include <queue> #include <stack> #include <set> #include <utility> #include <fstream> #include <cassert> #define INF 999999999999999999LL #define MOD 1000000007 #define MAX 202010 #define ALL 50 #define DEBUG false using namespace std; int n,m,d; set<int> S[MAX]; vector<int> T; bool visited[MAX]; int dfs(int v) { int pom = 1; visited[v] = true; for (auto neighour : S[v]) { if (!visited[neighour] && !S[neighour].empty()) { pom += dfs(neighour); } } return pom; } void dfs_collect(int v) { visited[v] = true; T.push_back(v); for (auto neighour : S[v]) { if (!visited[neighour] && !S[neighour].empty()) { dfs_collect(neighour); } } } int main() { scanf("%d %d %d", &n, &m, &d); int from, to; for (int i = 0; i < m; ++i) { scanf("%d %d", &from, &to); S[from].insert(to); S[to].insert(from); } queue<int> Q; for (int i = 1; i <= n; ++i) if (S[i].size() < d) Q.push(i); for (; !Q.empty(); Q.pop()) { int act = Q.front(); if (S[act].size() >= d) continue; for (auto neighour : S[act]) { S[neighour].erase(act); Q.push(neighour); } S[act].clear(); } for (int i = 0; i < MAX; ++i) visited[i] = false; int res = 0, start = -1; for (int i = 1; i <= n; ++i) { if (!visited[i] && !S[i].empty()) { int current = dfs(i); if (current > res) { res = current; start = i; } } } if (start == -1 || res <= d) { printf("NIE"); } else { for (int i = 0; i < MAX; ++i) visited[i] = false; // zbieramy dfs_collect(start); sort(T.begin(), T.end()); printf("%d\n", (int)T.size()); for (auto city : T) printf("%d ", city); } 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 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 | #include <iostream> #include <cstdio> #include <ctime> #include <cstdlib> #include <algorithm> #include <cmath> #include <vector> #include <map> #include <queue> #include <stack> #include <set> #include <utility> #include <fstream> #include <cassert> #define INF 999999999999999999LL #define MOD 1000000007 #define MAX 202010 #define ALL 50 #define DEBUG false using namespace std; int n,m,d; set<int> S[MAX]; vector<int> T; bool visited[MAX]; int dfs(int v) { int pom = 1; visited[v] = true; for (auto neighour : S[v]) { if (!visited[neighour] && !S[neighour].empty()) { pom += dfs(neighour); } } return pom; } void dfs_collect(int v) { visited[v] = true; T.push_back(v); for (auto neighour : S[v]) { if (!visited[neighour] && !S[neighour].empty()) { dfs_collect(neighour); } } } int main() { scanf("%d %d %d", &n, &m, &d); int from, to; for (int i = 0; i < m; ++i) { scanf("%d %d", &from, &to); S[from].insert(to); S[to].insert(from); } queue<int> Q; for (int i = 1; i <= n; ++i) if (S[i].size() < d) Q.push(i); for (; !Q.empty(); Q.pop()) { int act = Q.front(); if (S[act].size() >= d) continue; for (auto neighour : S[act]) { S[neighour].erase(act); Q.push(neighour); } S[act].clear(); } for (int i = 0; i < MAX; ++i) visited[i] = false; int res = 0, start = -1; for (int i = 1; i <= n; ++i) { if (!visited[i] && !S[i].empty()) { int current = dfs(i); if (current > res) { res = current; start = i; } } } if (start == -1 || res <= d) { printf("NIE"); } else { for (int i = 0; i < MAX; ++i) visited[i] = false; // zbieramy dfs_collect(start); sort(T.begin(), T.end()); printf("%d\n", (int)T.size()); for (auto city : T) printf("%d ", city); } return 0; } |