#include<cstdio> #include<vector> #include<algorithm> #define maks 200001 using namespace std; vector<int>drogi[maks]; vector<int>sciezki[maks]; int wielkosc[maks]; bool zabity[maks]; bool odwiedzony[maks]; int tab[maks]; int t[maks]; int k,d; void zabijaj(int v) { zabity[v]=true; for(int a=0; a<drogi[v].size(); a++) { if(!zabity[drogi[v][a]]) { wielkosc[drogi[v][a]]--; if(wielkosc[drogi[v][a]]<d) zabijaj(drogi[v][a]); } } } void sprawdzaj(int v) { odwiedzony[v]=true; k++; t[k]=v; for(int a=0; a<sciezki[v].size(); a++) { if(!odwiedzony[sciezki[v][a]]) { sprawdzaj(sciezki[v][a]); } } } int main() { int n,m,ile=0,x,y,maksi=0; scanf("%d%d%d",&n,&m,&d); int rozpatruje[n+1]; for(int a=1; a<=m; a++) { scanf("%d%d",&x,&y); drogi[x].push_back(y); drogi[y].push_back(x); } for(int a=1; a<=n; a++) { wielkosc[a]=drogi[a].size(); if(wielkosc[a]<d) { ile++; rozpatruje[ile]=a; } } if(ile>0) { for(int a=1; a<=ile; a++) { if(!zabity[rozpatruje[a]]) zabijaj(rozpatruje[a]); } for(int a=1; a<=n; a++) { for(int b=0; b<drogi[a].size(); b++) { if(!zabity[drogi[a][b]]) sciezki[a].push_back(drogi[a][b]); } } } else { for(int a=1; a<=n; a++) { for(int b=0; b<drogi[a].size(); b++) sciezki[a].push_back(drogi[a][b]); } } for(int a=1; a<=n; a++) { if(!odwiedzony[a]) { if(!zabity[a]) { k=-1; sprawdzaj(a); if(k+1>maksi) { maksi=k+1; for(int a=0; a<maksi; a++) { tab[a]=t[a]; } } } } } if(maksi==0) printf("NIE"); else { printf("%d\n",maksi); sort(tab,tab+maksi); for(int a=0; a<maksi; a++) printf("%d ",tab[a]); } }
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 | #include<cstdio> #include<vector> #include<algorithm> #define maks 200001 using namespace std; vector<int>drogi[maks]; vector<int>sciezki[maks]; int wielkosc[maks]; bool zabity[maks]; bool odwiedzony[maks]; int tab[maks]; int t[maks]; int k,d; void zabijaj(int v) { zabity[v]=true; for(int a=0; a<drogi[v].size(); a++) { if(!zabity[drogi[v][a]]) { wielkosc[drogi[v][a]]--; if(wielkosc[drogi[v][a]]<d) zabijaj(drogi[v][a]); } } } void sprawdzaj(int v) { odwiedzony[v]=true; k++; t[k]=v; for(int a=0; a<sciezki[v].size(); a++) { if(!odwiedzony[sciezki[v][a]]) { sprawdzaj(sciezki[v][a]); } } } int main() { int n,m,ile=0,x,y,maksi=0; scanf("%d%d%d",&n,&m,&d); int rozpatruje[n+1]; for(int a=1; a<=m; a++) { scanf("%d%d",&x,&y); drogi[x].push_back(y); drogi[y].push_back(x); } for(int a=1; a<=n; a++) { wielkosc[a]=drogi[a].size(); if(wielkosc[a]<d) { ile++; rozpatruje[ile]=a; } } if(ile>0) { for(int a=1; a<=ile; a++) { if(!zabity[rozpatruje[a]]) zabijaj(rozpatruje[a]); } for(int a=1; a<=n; a++) { for(int b=0; b<drogi[a].size(); b++) { if(!zabity[drogi[a][b]]) sciezki[a].push_back(drogi[a][b]); } } } else { for(int a=1; a<=n; a++) { for(int b=0; b<drogi[a].size(); b++) sciezki[a].push_back(drogi[a][b]); } } for(int a=1; a<=n; a++) { if(!odwiedzony[a]) { if(!zabity[a]) { k=-1; sprawdzaj(a); if(k+1>maksi) { maksi=k+1; for(int a=0; a<maksi; a++) { tab[a]=t[a]; } } } } } if(maksi==0) printf("NIE"); else { printf("%d\n",maksi); sort(tab,tab+maksi); for(int a=0; a<maksi; a++) printf("%d ",tab[a]); } } |