//Pawel Kura #include <cstdio> #include <set> #include <algorithm> #include <queue> #include <cassert> using namespace std; const int MAXN = 200000; int n, m, d; int deg[MAXN]; bool del[MAXN]; bool vis[MAXN]; vector<int> G[MAXN]; //set<pair<int,int>> S; vector<int> S; void dfs(int x, vector<int> &res) { vis[x] = true; res.push_back(x); for (auto y: G[x]) { if (!vis[y] && !del[y]) { dfs(y, res); } } } int main() { scanf("%d %d %d", &n ,&m, &d); for (int i = 0; i < m; i++) { int x, y; scanf("%d %d", &x, &y); x--; y--; G[x].push_back(y); G[y].push_back(x); deg[x]++; deg[y]++; } //for (int i = 0; i < n; i++) S.insert({deg[i], i}); for (int i =0 ; i < n; i++) if (deg[i] < d) S.push_back(i), del[i] = true; while (!S.empty()) { auto p = S.back(); //if (deg[ >= d) break; //S.erase(S.begin()); S.pop_back(); for (auto v: G[p]) { deg[v]--; if (deg[v] < d && !del[v]) { del[v] = true; S.push_back(v); } /*S.erase({deg[v], v}); deg[v]--; S.insert({deg[v], v});*/ } } vector<int> longest; for (int i = 0; i < n; i++) { if (del[i] || vis[i]) continue; vector<int> res; dfs(i, res); if (res.size() > longest.size()) longest = res; } if (longest.size() == 0) printf("NIE"); else { vector<bool> jest(n); for (auto x: longest) jest[x] = true; printf("%d\n", longest.size()); for (int i = 0; i < n; i++) { if (jest[i]) printf("%d ", i + 1); } } puts(""); 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 | //Pawel Kura #include <cstdio> #include <set> #include <algorithm> #include <queue> #include <cassert> using namespace std; const int MAXN = 200000; int n, m, d; int deg[MAXN]; bool del[MAXN]; bool vis[MAXN]; vector<int> G[MAXN]; //set<pair<int,int>> S; vector<int> S; void dfs(int x, vector<int> &res) { vis[x] = true; res.push_back(x); for (auto y: G[x]) { if (!vis[y] && !del[y]) { dfs(y, res); } } } int main() { scanf("%d %d %d", &n ,&m, &d); for (int i = 0; i < m; i++) { int x, y; scanf("%d %d", &x, &y); x--; y--; G[x].push_back(y); G[y].push_back(x); deg[x]++; deg[y]++; } //for (int i = 0; i < n; i++) S.insert({deg[i], i}); for (int i =0 ; i < n; i++) if (deg[i] < d) S.push_back(i), del[i] = true; while (!S.empty()) { auto p = S.back(); //if (deg[ >= d) break; //S.erase(S.begin()); S.pop_back(); for (auto v: G[p]) { deg[v]--; if (deg[v] < d && !del[v]) { del[v] = true; S.push_back(v); } /*S.erase({deg[v], v}); deg[v]--; S.insert({deg[v], v});*/ } } vector<int> longest; for (int i = 0; i < n; i++) { if (del[i] || vis[i]) continue; vector<int> res; dfs(i, res); if (res.size() > longest.size()) longest = res; } if (longest.size() == 0) printf("NIE"); else { vector<bool> jest(n); for (auto x: longest) jest[x] = true; printf("%d\n", longest.size()); for (int i = 0; i < n; i++) { if (jest[i]) printf("%d ", i + 1); } } puts(""); return 0; } |