#include <iostream> #include <vector> #include <algorithm> using namespace std; int tymczas; vector <int> wynik; bool x; vector <int> polaczenia[200005]; pair <int, int> maks; int liczba[200005]; bool odwiedzone[200005]; void DFS1( int wierzcholek) { if(x==1) { wynik.push_back(wierzcholek); } else tymczas++; odwiedzone[wierzcholek]=1; for(int t=0; t<polaczenia[wierzcholek].size(); t++) { if(odwiedzone[polaczenia[wierzcholek][t]]==0) DFS1(polaczenia[wierzcholek][t]); } return ; } int main() { ios_base::sync_with_stdio(0); //magiczna linijka cin.tie(NULL); x=0; int miasta, drogi, d; cin >> miasta >> drogi >> d; for(int i=1; i<=drogi; i++) { int a,b; cin >> a >> b; polaczenia[a].push_back(b); polaczenia[b].push_back(a); liczba[a]++; liczba[b]++; } for(int i=1; i<=miasta; i++) { if(liczba[i]<d and odwiedzone[liczba[i]]==0) { odwiedzone[i]=1; for(int k=0; k<polaczenia[i].size(); k++) { liczba[polaczenia[i][k]]--; } i=1; } } // powinny zostać same wierzcholki które mają d+ krawędzi maks.first=0; maks.second=0; for(int i=1; i<=miasta; i++) { tymczas=0; if(odwiedzone[i]==0 and liczba[i]>=d) { DFS1(i); } if(tymczas>maks.first) { maks.first=tymczas; maks.second=i; } } if(maks.first==0) { cout << "NIE"; return 0; } cout << maks.first << "\n"; x=1; for(int u=1; u<=miasta; u++) { if(liczba[u]>=d) { odwiedzone[u]=0; } } DFS1(maks.second); sort(wynik.begin(), wynik.end()); for(int i=0; i<wynik.size(); i++) { cout << wynik[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 | #include <iostream> #include <vector> #include <algorithm> using namespace std; int tymczas; vector <int> wynik; bool x; vector <int> polaczenia[200005]; pair <int, int> maks; int liczba[200005]; bool odwiedzone[200005]; void DFS1( int wierzcholek) { if(x==1) { wynik.push_back(wierzcholek); } else tymczas++; odwiedzone[wierzcholek]=1; for(int t=0; t<polaczenia[wierzcholek].size(); t++) { if(odwiedzone[polaczenia[wierzcholek][t]]==0) DFS1(polaczenia[wierzcholek][t]); } return ; } int main() { ios_base::sync_with_stdio(0); //magiczna linijka cin.tie(NULL); x=0; int miasta, drogi, d; cin >> miasta >> drogi >> d; for(int i=1; i<=drogi; i++) { int a,b; cin >> a >> b; polaczenia[a].push_back(b); polaczenia[b].push_back(a); liczba[a]++; liczba[b]++; } for(int i=1; i<=miasta; i++) { if(liczba[i]<d and odwiedzone[liczba[i]]==0) { odwiedzone[i]=1; for(int k=0; k<polaczenia[i].size(); k++) { liczba[polaczenia[i][k]]--; } i=1; } } // powinny zostać same wierzcholki które mają d+ krawędzi maks.first=0; maks.second=0; for(int i=1; i<=miasta; i++) { tymczas=0; if(odwiedzone[i]==0 and liczba[i]>=d) { DFS1(i); } if(tymczas>maks.first) { maks.first=tymczas; maks.second=i; } } if(maks.first==0) { cout << "NIE"; return 0; } cout << maks.first << "\n"; x=1; for(int u=1; u<=miasta; u++) { if(liczba[u]>=d) { odwiedzone[u]=0; } } DFS1(maks.second); sort(wynik.begin(), wynik.end()); for(int i=0; i<wynik.size(); i++) { cout << wynik[i] << " "; } return 0; } |