#include <bits/stdc++.h> using namespace std; const int MX = 2e5 + 5; int deg[MX], n, m, d; vector<int> ile; bool wyrz[MX], vis[MX]; vector<int> adj[MX]; void wyrzuc(int v) { wyrz[v] = true; for (int i = 0; i < adj[v].size(); ++ i) { int u = adj[v][i]; if (!wyrz[u]) { deg[u] --; if (deg[u] < d) wyrzuc(u); } } } void dfs(int v) { vis[v] = true; ile.push_back(v); for (int i = 0; i < adj[v].size(); ++ i) if (!vis[adj[v][i]] && !wyrz[adj[v][i]]) dfs(adj[v][i]); } int main() { scanf("%d%d%d", &n, &m, &d); while (m--) { int a, b; scanf("%d%d", &a, &b); adj[a].push_back(b); adj[b].push_back(a); deg[a] ++; deg[b] ++; } for (int i = 1; i <= n; ++ i) if (!wyrz[i] && deg[i] < d) wyrzuc(i); vector<int> res = {}; for (int i = 1; i <= n; ++ i) if (!wyrz[i] && !vis[i]) { ile.clear(); dfs(i); if (ile.size() > res.size()) res = ile; } if (res.size() > 0) { printf("%d\n", res.size()); for (int i = 0; i < res.size(); ++ i) printf("%d ", res[i]); puts(""); } else puts("NIE"); 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 | #include <bits/stdc++.h> using namespace std; const int MX = 2e5 + 5; int deg[MX], n, m, d; vector<int> ile; bool wyrz[MX], vis[MX]; vector<int> adj[MX]; void wyrzuc(int v) { wyrz[v] = true; for (int i = 0; i < adj[v].size(); ++ i) { int u = adj[v][i]; if (!wyrz[u]) { deg[u] --; if (deg[u] < d) wyrzuc(u); } } } void dfs(int v) { vis[v] = true; ile.push_back(v); for (int i = 0; i < adj[v].size(); ++ i) if (!vis[adj[v][i]] && !wyrz[adj[v][i]]) dfs(adj[v][i]); } int main() { scanf("%d%d%d", &n, &m, &d); while (m--) { int a, b; scanf("%d%d", &a, &b); adj[a].push_back(b); adj[b].push_back(a); deg[a] ++; deg[b] ++; } for (int i = 1; i <= n; ++ i) if (!wyrz[i] && deg[i] < d) wyrzuc(i); vector<int> res = {}; for (int i = 1; i <= n; ++ i) if (!wyrz[i] && !vis[i]) { ile.clear(); dfs(i); if (ile.size() > res.size()) res = ile; } if (res.size() > 0) { printf("%d\n", res.size()); for (int i = 0; i < res.size(); ++ i) printf("%d ", res[i]); puts(""); } else puts("NIE"); return 0; } |