#include <bits/stdc++.h> using namespace std; vector<int> graf[200003]; bool p; bitset<200003> odw; int wierzcholki[200003],d,wynik=0,zbior[200003],zmienna; void dfs(int a) { odw[a]=true; for(int i=0;i<graf[a].size();i++) { if(odw[graf[a][i]]==false) { wierzcholki[graf[a][i]]--; if(wierzcholki[graf[a][i]]<d) { dfs(graf[a][i]); } } } } void dfs2(int a,int x) { odw[a]=true; zmienna++; zbior[zmienna]=a; //tab[a]=x; /*if(x>wynik) { wynik=x; p=true; }*/ for(int i=0;i<graf[a].size();i++) { if(odw[graf[a][i]]==false) { dfs2(graf[a][i], x+1); } } } int main() { int n,m,a,b; scanf("%d %d %d", &n, &m, &d); for(int i=0;i<m;i++) { scanf("%d %d", &a, &b); graf[a].push_back(b); graf[b].push_back(a); } for(int i=1;i<=n;i++) { wierzcholki[i]=graf[i].size(); //cout<<wierzcholki[i]<<" "; } for(int i=1;i<=n;i++) { if(wierzcholki[i]<d && odw[i]==false) { dfs(i); } } //cout<<endl; /* for(int i=1;i<=n;i++) { cout<<i<<" "<<odw[i]<<endl; } */ for(int i=1;i<=n;i++) { if(odw[i]==false) { zmienna=0; dfs2(i,1); if(zmienna>wynik) { swap(wierzcholki,zbior); wynik=zmienna; } } } if(wynik==0) { printf("NIE"); return 0; } else { sort(wierzcholki+1, wierzcholki+wynik+1); printf("%d\n", wynik); for(int i=1;i<=wynik;i++) { printf("%d ", wierzcholki[i]); } } return 0; }
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 119 120 121 122 123 124 125 126 127 128 129 130 131 | #include <bits/stdc++.h> using namespace std; vector<int> graf[200003]; bool p; bitset<200003> odw; int wierzcholki[200003],d,wynik=0,zbior[200003],zmienna; void dfs(int a) { odw[a]=true; for(int i=0;i<graf[a].size();i++) { if(odw[graf[a][i]]==false) { wierzcholki[graf[a][i]]--; if(wierzcholki[graf[a][i]]<d) { dfs(graf[a][i]); } } } } void dfs2(int a,int x) { odw[a]=true; zmienna++; zbior[zmienna]=a; //tab[a]=x; /*if(x>wynik) { wynik=x; p=true; }*/ for(int i=0;i<graf[a].size();i++) { if(odw[graf[a][i]]==false) { dfs2(graf[a][i], x+1); } } } int main() { int n,m,a,b; scanf("%d %d %d", &n, &m, &d); for(int i=0;i<m;i++) { scanf("%d %d", &a, &b); graf[a].push_back(b); graf[b].push_back(a); } for(int i=1;i<=n;i++) { wierzcholki[i]=graf[i].size(); //cout<<wierzcholki[i]<<" "; } for(int i=1;i<=n;i++) { if(wierzcholki[i]<d && odw[i]==false) { dfs(i); } } //cout<<endl; /* for(int i=1;i<=n;i++) { cout<<i<<" "<<odw[i]<<endl; } */ for(int i=1;i<=n;i++) { if(odw[i]==false) { zmienna=0; dfs2(i,1); if(zmienna>wynik) { swap(wierzcholki,zbior); wynik=zmienna; } } } if(wynik==0) { printf("NIE"); return 0; } else { sort(wierzcholki+1, wierzcholki+wynik+1); printf("%d\n", wynik); for(int i=1;i<=wynik;i++) { printf("%d ", wierzcholki[i]); } } return 0; } |