#include <cstdio> #include <vector> #include <queue> using namespace std; const int N = 200001; vector<int> g[N]; bool vis[N]; int deg[N]; vector<int> vec; void dfs(int v) { if(vis[v]) return; vis[v] = true; vec.push_back(v); for(int u: g[v]) dfs(u); } int main() { int n, m, d; scanf("%d %d %d", &n, &m, &d); while(m--) { int a, b; scanf("%d %d", &a, &b); g[a].push_back(b); g[b].push_back(a); deg[a]++; deg[b]++; } queue<int> q; for(int i = 1; i <= n; i++) if(!vis[i] && deg[i] < d) { vis[i] = true; q.push(i); } while(!q.empty()) { int v = q.front(); q.pop(); for(int u: g[v]) if(!vis[u] && --deg[u] < d) { vis[u] = true; q.push(u); } } vector<int> ans; for(int i = 1; i <= n; i++) { dfs(i); if(vec.size() > ans.size()) ans = vec; } if(ans.size()) { printf("%d\n", ans.size()); for(int x: ans) printf("%d ", x); puts(""); } 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 | #include <cstdio> #include <vector> #include <queue> using namespace std; const int N = 200001; vector<int> g[N]; bool vis[N]; int deg[N]; vector<int> vec; void dfs(int v) { if(vis[v]) return; vis[v] = true; vec.push_back(v); for(int u: g[v]) dfs(u); } int main() { int n, m, d; scanf("%d %d %d", &n, &m, &d); while(m--) { int a, b; scanf("%d %d", &a, &b); g[a].push_back(b); g[b].push_back(a); deg[a]++; deg[b]++; } queue<int> q; for(int i = 1; i <= n; i++) if(!vis[i] && deg[i] < d) { vis[i] = true; q.push(i); } while(!q.empty()) { int v = q.front(); q.pop(); for(int u: g[v]) if(!vis[u] && --deg[u] < d) { vis[u] = true; q.push(u); } } vector<int> ans; for(int i = 1; i <= n; i++) { dfs(i); if(vec.size() > ans.size()) ans = vec; } if(ans.size()) { printf("%d\n", ans.size()); for(int x: ans) printf("%d ", x); puts(""); } else puts("NIE"); } |