#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int> vi; typedef pair<int, int> pii; #define fi first #define se second #define mp make_pair #define pb push_back const int INF = 1 << 30; const double EPS = 1e-12; const int N=200042; int deg[N], bad[N]; vi v[N]; int dfs(int x, int st) { bad[x]=st; int ret=1; for(auto nxt : v[x]) { if(!bad[nxt]) ret+=dfs(nxt,st); } return ret; } 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); v[a].pb(b); v[b].pb(a); deg[a]++; deg[b]++; } queue<int> nope; for(int i=1;i<=n;i++) { if(deg[i]<d) { nope.push(i); bad[i]=-1; } } while(nope.size()) { int cur=nope.front(); nope.pop(); for(auto nxt : v[cur]) { deg[nxt]--; if(!bad[nxt] && deg[nxt]<d) { bad[nxt]=-1; nope.push(nxt); } } } int ans=0, st=0; for(int i=1;i<=n;i++) { if(!bad[i]) { int cur=dfs(i,i); if(cur>ans) { ans=cur; st=i; } } } if(ans) { printf("%d\n", ans); for(int i=1;i<=n;i++) if(bad[i]==st) printf("%d ",i); } else printf("NIE\n"); }
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 | #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int> vi; typedef pair<int, int> pii; #define fi first #define se second #define mp make_pair #define pb push_back const int INF = 1 << 30; const double EPS = 1e-12; const int N=200042; int deg[N], bad[N]; vi v[N]; int dfs(int x, int st) { bad[x]=st; int ret=1; for(auto nxt : v[x]) { if(!bad[nxt]) ret+=dfs(nxt,st); } return ret; } 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); v[a].pb(b); v[b].pb(a); deg[a]++; deg[b]++; } queue<int> nope; for(int i=1;i<=n;i++) { if(deg[i]<d) { nope.push(i); bad[i]=-1; } } while(nope.size()) { int cur=nope.front(); nope.pop(); for(auto nxt : v[cur]) { deg[nxt]--; if(!bad[nxt] && deg[nxt]<d) { bad[nxt]=-1; nope.push(nxt); } } } int ans=0, st=0; for(int i=1;i<=n;i++) { if(!bad[i]) { int cur=dfs(i,i); if(cur>ans) { ans=cur; st=i; } } } if(ans) { printf("%d\n", ans); for(int i=1;i<=n;i++) if(bad[i]==st) printf("%d ",i); } else printf("NIE\n"); } |