#include <iostream> #include <algorithm> #include <vector> #include <string> #include <stack> #include <queue> #include <cmath> #include <cstdio> #include <set> #include <iomanip> using namespace std; typedef vector<int> VI; typedef long long LL; #define FOR(x,b,e) for(int x = (b) ; x <= (e) ; ++x) #define FORD(x,b,e) for(int x = (b) ; x >= (e) ; --x) #define REP(x,e) for(int x = 0 ; x < (e) ; ++x) #define VAR(v,n) _typeof(n) v=(n) #define ALL(c) (c).begin(),(c).end() #define SIZE(x) ((int)(x).size()) #define FOREACH(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i) #define PB push_back const int inf = 1000000000,maxn=200005; VI g[maxn]; bool kosz[maxn]; int deg[maxn]; int n,m,d; int skladowe[maxn]; void bfs(int x,int skl) { skladowe[x]=skl; VI kol; kol.PB(x); REP(i,SIZE(kol)) { int u=kol[i]; REP(j,SIZE(g[u]))if(skladowe[g[u][j]]==0) { skladowe[g[u][j]]=skl; kol.PB(g[u][j]); } } } int counter[maxn]; int main() { ios::sync_with_stdio(0); cin >> n >> m >> d; while(m--) { int a,b; cin >> a >> b; g[a-1].PB(b-1); g[b-1].PB(a-1); } REP(i,n)deg[i]=SIZE(g[i]); VI q; REP(i,n)if(SIZE(g[i])<d) { q.PB(i); kosz[i]=1; } REP(i,SIZE(q)) { int x=q[i]; REP(j,SIZE(g[x])) { deg[g[x][j]]--; if(deg[g[x][j]]<d&&kosz[g[x][j]]==0) { q.PB(g[x][j]); kosz[g[x][j]]=1; } } } REP(i,n) { if(kosz[i])g[i].clear(); REP(j,SIZE(g[i]))if(kosz[g[i][j]]) { swap(g[i][j],g[i].back()); g[i].pop_back(); } } int s=1; REP(i,n)if(!kosz[i]) { if(skladowe[i]==0)bfs(i,s++); counter[skladowe[i]]++; } int maks=-1,ind; FOR(i,1,s-1)if(counter[i]>maks) { maks=counter[i]; ind=i; } if(maks==-1) { cout<<"NIE"; return 0; } cout << maks<<"\n"; REP(i,n)if(skladowe[i]==ind)cout<< i+1 <<" "; }
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 | #include <iostream> #include <algorithm> #include <vector> #include <string> #include <stack> #include <queue> #include <cmath> #include <cstdio> #include <set> #include <iomanip> using namespace std; typedef vector<int> VI; typedef long long LL; #define FOR(x,b,e) for(int x = (b) ; x <= (e) ; ++x) #define FORD(x,b,e) for(int x = (b) ; x >= (e) ; --x) #define REP(x,e) for(int x = 0 ; x < (e) ; ++x) #define VAR(v,n) _typeof(n) v=(n) #define ALL(c) (c).begin(),(c).end() #define SIZE(x) ((int)(x).size()) #define FOREACH(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i) #define PB push_back const int inf = 1000000000,maxn=200005; VI g[maxn]; bool kosz[maxn]; int deg[maxn]; int n,m,d; int skladowe[maxn]; void bfs(int x,int skl) { skladowe[x]=skl; VI kol; kol.PB(x); REP(i,SIZE(kol)) { int u=kol[i]; REP(j,SIZE(g[u]))if(skladowe[g[u][j]]==0) { skladowe[g[u][j]]=skl; kol.PB(g[u][j]); } } } int counter[maxn]; int main() { ios::sync_with_stdio(0); cin >> n >> m >> d; while(m--) { int a,b; cin >> a >> b; g[a-1].PB(b-1); g[b-1].PB(a-1); } REP(i,n)deg[i]=SIZE(g[i]); VI q; REP(i,n)if(SIZE(g[i])<d) { q.PB(i); kosz[i]=1; } REP(i,SIZE(q)) { int x=q[i]; REP(j,SIZE(g[x])) { deg[g[x][j]]--; if(deg[g[x][j]]<d&&kosz[g[x][j]]==0) { q.PB(g[x][j]); kosz[g[x][j]]=1; } } } REP(i,n) { if(kosz[i])g[i].clear(); REP(j,SIZE(g[i]))if(kosz[g[i][j]]) { swap(g[i][j],g[i].back()); g[i].pop_back(); } } int s=1; REP(i,n)if(!kosz[i]) { if(skladowe[i]==0)bfs(i,s++); counter[skladowe[i]]++; } int maks=-1,ind; FOR(i,1,s-1)if(counter[i]>maks) { maks=counter[i]; ind=i; } if(maks==-1) { cout<<"NIE"; return 0; } cout << maks<<"\n"; REP(i,n)if(skladowe[i]==ind)cout<< i+1 <<" "; } |