#include <cstdio> #include <algorithm> #include <vector> #define fi first #define se second using namespace std; const int MAXN=200005,P2=(1<<18),MP=(1<<19)+5,INF=(int)1e9+5; pair <int,int> T[MP]; vector <int> G[MAXN]; int R[MAXN],wie[MAXN],wykozdrolone[MAXN],res[MAXN]; int n,m,d,a,b,s,best,wzor,curr; int Find(int x) { if(R[x]==x) return x; R[x]=Find(R[x]); return R[x]; } void Union(int a, int b) { int c=Find(a),d=Find(b); if(c!=d) { if(wie[c]>wie[d]) { wie[c]+=wie[d]; R[d]=c; } else { wie[d]+=wie[c]; R[c]=d; } } } void add(int pos, int val) { pos+=P2; T[pos].fi+=val; while(pos>1) { pos>>=1; T[pos]=min(T[pos<<1],T[1+(pos<<1)]); } } int main() { scanf("%d%d%d", &n, &m, &d); for(int i=P2; i<MP; ++i) T[i]=make_pair(INF,i-P2); for(int i=P2-1; i>0; --i) T[i]=min(T[i<<1],T[1+(i<<1)]); for(int i=1; i<=n; ++i) { R[i]=i; add(i,-INF); } for(int i=0; i<m; ++i) { scanf("%d%d", &a, &b); G[a].push_back(b); G[b].push_back(a); add(a,1); add(b,1); } while(T[1].fi<d) { curr=T[1].se; wykozdrolone[curr]=1; s=G[curr].size(); for(int i=0; i<s; ++i) add(G[curr][i],-1); add(curr,INF); } for(int i=1; i<=n; ++i) { if(!wykozdrolone[i]) { s=G[i].size(); for(int j=0; j<s; ++j) { if(!wykozdrolone[G[i][j]]) Union(i,G[i][j]); } } } for(int i=1; i<=n; ++i) ++res[Find(i)]; for(int i=1; i<=n; ++i) { if(res[i]>best) { best=res[i]; wzor=Find(i); } } if(best>1) { printf("%d\n", best); } else { printf("NIE"); return 0; } for(int i=1; i<=n; ++i) { if(Find(i)==wzor) printf("%d ", i); } }
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 116 117 118 | #include <cstdio> #include <algorithm> #include <vector> #define fi first #define se second using namespace std; const int MAXN=200005,P2=(1<<18),MP=(1<<19)+5,INF=(int)1e9+5; pair <int,int> T[MP]; vector <int> G[MAXN]; int R[MAXN],wie[MAXN],wykozdrolone[MAXN],res[MAXN]; int n,m,d,a,b,s,best,wzor,curr; int Find(int x) { if(R[x]==x) return x; R[x]=Find(R[x]); return R[x]; } void Union(int a, int b) { int c=Find(a),d=Find(b); if(c!=d) { if(wie[c]>wie[d]) { wie[c]+=wie[d]; R[d]=c; } else { wie[d]+=wie[c]; R[c]=d; } } } void add(int pos, int val) { pos+=P2; T[pos].fi+=val; while(pos>1) { pos>>=1; T[pos]=min(T[pos<<1],T[1+(pos<<1)]); } } int main() { scanf("%d%d%d", &n, &m, &d); for(int i=P2; i<MP; ++i) T[i]=make_pair(INF,i-P2); for(int i=P2-1; i>0; --i) T[i]=min(T[i<<1],T[1+(i<<1)]); for(int i=1; i<=n; ++i) { R[i]=i; add(i,-INF); } for(int i=0; i<m; ++i) { scanf("%d%d", &a, &b); G[a].push_back(b); G[b].push_back(a); add(a,1); add(b,1); } while(T[1].fi<d) { curr=T[1].se; wykozdrolone[curr]=1; s=G[curr].size(); for(int i=0; i<s; ++i) add(G[curr][i],-1); add(curr,INF); } for(int i=1; i<=n; ++i) { if(!wykozdrolone[i]) { s=G[i].size(); for(int j=0; j<s; ++j) { if(!wykozdrolone[G[i][j]]) Union(i,G[i][j]); } } } for(int i=1; i<=n; ++i) ++res[Find(i)]; for(int i=1; i<=n; ++i) { if(res[i]>best) { best=res[i]; wzor=Find(i); } } if(best>1) { printf("%d\n", best); } else { printf("NIE"); return 0; } for(int i=1; i<=n; ++i) { if(Find(i)==wzor) printf("%d ", i); } } |