#include <cstdio> #include <vector> #include <queue> #include <algorithm> #define MAKS 200010 #define f first #define s second #define mp make_pair using namespace std; typedef pair<int,int> para; vector<int> sas[MAKS]; bool istnieje[MAKS]; bool bylo[MAKS]; int st[MAKS]; struct cmp { bool operator()(const para& a, const para& b) { if(a.s!=b.s)return a.s>b.s; return a.f>b.f; } }; priority_queue<para, vector<para>, cmp> q; int dfs(int v) { bylo[v]=true; int wyn=1; for(int i=0;i<sas[v].size();i++) { if(!istnieje[sas[v][i]])continue; if(!bylo[sas[v][i]])wyn+=dfs(sas[v][i]); } return wyn; } vector<int> skladowa; void dfs2(int v) { bylo[v]=true; skladowa.push_back(v); for(int i=0;i<sas[v].size();i++) { if(!istnieje[sas[v][i]])continue; if(!bylo[sas[v][i]])dfs2(sas[v][i]); } } int main() { int n,m,d; scanf("%d %d %d",&n,&m,&d); for(int i=1;i<=n;i++)istnieje[i]=true; for(int i=0;i<m;i++) { int a,b; scanf("%d %d",&a,&b); sas[a].push_back(b); sas[b].push_back(a); st[a]++; st[b]++; } for(int i=1;i<=n;i++)q.push(make_pair(i,st[i])); while(!q.empty()) { para p=q.top(); q.pop(); if(p.s != st[p.f])continue; int v=p.f; if(st[v]<d) { istnieje[v]=false; for(int i=0;i<sas[v].size();i++) { if(!istnieje[sas[v][i]])continue; st[sas[v][i]]--; q.push(mp(sas[v][i],st[sas[v][i]])); } } } int naj=0; int kto=0; for(int i=1;i<=n;i++) { if(!istnieje[i])continue; if(!bylo[i]) { int kand=dfs(i); if(kand>naj) { naj=kand; kto=i; } } } if(naj==0)puts("NIE"); else { skladowa.clear(); for(int i=1;i<=n;i++)bylo[i]=false; dfs2(kto); sort(skladowa.begin(),skladowa.end()); printf("%d\n",naj); for(int i=0;i<skladowa.size();i++)printf("%d ",skladowa[i]); puts(""); } }
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 | #include <cstdio> #include <vector> #include <queue> #include <algorithm> #define MAKS 200010 #define f first #define s second #define mp make_pair using namespace std; typedef pair<int,int> para; vector<int> sas[MAKS]; bool istnieje[MAKS]; bool bylo[MAKS]; int st[MAKS]; struct cmp { bool operator()(const para& a, const para& b) { if(a.s!=b.s)return a.s>b.s; return a.f>b.f; } }; priority_queue<para, vector<para>, cmp> q; int dfs(int v) { bylo[v]=true; int wyn=1; for(int i=0;i<sas[v].size();i++) { if(!istnieje[sas[v][i]])continue; if(!bylo[sas[v][i]])wyn+=dfs(sas[v][i]); } return wyn; } vector<int> skladowa; void dfs2(int v) { bylo[v]=true; skladowa.push_back(v); for(int i=0;i<sas[v].size();i++) { if(!istnieje[sas[v][i]])continue; if(!bylo[sas[v][i]])dfs2(sas[v][i]); } } int main() { int n,m,d; scanf("%d %d %d",&n,&m,&d); for(int i=1;i<=n;i++)istnieje[i]=true; for(int i=0;i<m;i++) { int a,b; scanf("%d %d",&a,&b); sas[a].push_back(b); sas[b].push_back(a); st[a]++; st[b]++; } for(int i=1;i<=n;i++)q.push(make_pair(i,st[i])); while(!q.empty()) { para p=q.top(); q.pop(); if(p.s != st[p.f])continue; int v=p.f; if(st[v]<d) { istnieje[v]=false; for(int i=0;i<sas[v].size();i++) { if(!istnieje[sas[v][i]])continue; st[sas[v][i]]--; q.push(mp(sas[v][i],st[sas[v][i]])); } } } int naj=0; int kto=0; for(int i=1;i<=n;i++) { if(!istnieje[i])continue; if(!bylo[i]) { int kand=dfs(i); if(kand>naj) { naj=kand; kto=i; } } } if(naj==0)puts("NIE"); else { skladowa.clear(); for(int i=1;i<=n;i++)bylo[i]=false; dfs2(kto); sort(skladowa.begin(),skladowa.end()); printf("%d\n",naj); for(int i=0;i<skladowa.size();i++)printf("%d ",skladowa[i]); puts(""); } } |