#include<iostream> #include<vector> #include<queue> #include<algorithm> using namespace std; const int max_n=200*1000+9; struct city{ int n; int d; }; bool operator<(city a, city b) { return a.d > b.d; return true; } vector<int> V[max_n]; int D[max_n]; //degree bool A[max_n]; //active int S[max_n]; //ss priority_queue< city > Q; int bfs(int n, int s) { queue< int > K; K.push(n); S[n] = s; int t = 1; while(!K.empty()) { int p = K.front(); K.pop(); for(int i = 0; i < V[p].size(); i++) { int j = V[p][i]; if(A[j] == true && S[j] == 0) { K.push(j); S[j]=s; t++; } } } return t; } int main() { ios_base::sync_with_stdio(0); int n, m, d; cin>>n>>m>>d; int a, b; for(int i = 1; i<=m; i++) { cin>>a>>b; V[a].push_back(b); V[b].push_back(a); } city k, l;//zmienne do trzymania city'ow for(int i = 1; i<=n; i++) { k.n = i; k.d = D[i] = V[i].size(); A[i] = true; Q.push(k); S[i] = 0; } while( Q.top().d < d) { k = Q.top(); Q.pop(); if(A[k.n] == true) { A[k.n] = false; for(int i = 0; i < V[k.n].size(); i++) { l.n = V[k.n][i]; if(A[ l.n ] == true) { D[ l.n ]-=1; l.d = D[ l.n ]; Q.push(l); } } } } int s = 1, t=0; vector<int> spojne; for(int i = 1; i<=n; i++) { if(S[i] == 0 && A[i] == true) { t=bfs(i, s); spojne.push_back(t); s++; } } int winner, w=0; for(int i = 0; i <spojne.size(); i++) { if(spojne[i] >= w) { winner = i+1; w = spojne[i]; } } if(w > 1 ) { cout<<w<<endl; priority_queue<int, vector<int>, greater<int> > ANS; for(int i = 1; i <=n; i++) if(S[i] == winner) ANS.push(i); while(!ANS.empty()) { cout<<ANS.top()<<" "; ANS.pop(); } cout<<endl; } else { cout<<"NIE"<<endl; } 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 | #include<iostream> #include<vector> #include<queue> #include<algorithm> using namespace std; const int max_n=200*1000+9; struct city{ int n; int d; }; bool operator<(city a, city b) { return a.d > b.d; return true; } vector<int> V[max_n]; int D[max_n]; //degree bool A[max_n]; //active int S[max_n]; //ss priority_queue< city > Q; int bfs(int n, int s) { queue< int > K; K.push(n); S[n] = s; int t = 1; while(!K.empty()) { int p = K.front(); K.pop(); for(int i = 0; i < V[p].size(); i++) { int j = V[p][i]; if(A[j] == true && S[j] == 0) { K.push(j); S[j]=s; t++; } } } return t; } int main() { ios_base::sync_with_stdio(0); int n, m, d; cin>>n>>m>>d; int a, b; for(int i = 1; i<=m; i++) { cin>>a>>b; V[a].push_back(b); V[b].push_back(a); } city k, l;//zmienne do trzymania city'ow for(int i = 1; i<=n; i++) { k.n = i; k.d = D[i] = V[i].size(); A[i] = true; Q.push(k); S[i] = 0; } while( Q.top().d < d) { k = Q.top(); Q.pop(); if(A[k.n] == true) { A[k.n] = false; for(int i = 0; i < V[k.n].size(); i++) { l.n = V[k.n][i]; if(A[ l.n ] == true) { D[ l.n ]-=1; l.d = D[ l.n ]; Q.push(l); } } } } int s = 1, t=0; vector<int> spojne; for(int i = 1; i<=n; i++) { if(S[i] == 0 && A[i] == true) { t=bfs(i, s); spojne.push_back(t); s++; } } int winner, w=0; for(int i = 0; i <spojne.size(); i++) { if(spojne[i] >= w) { winner = i+1; w = spojne[i]; } } if(w > 1 ) { cout<<w<<endl; priority_queue<int, vector<int>, greater<int> > ANS; for(int i = 1; i <=n; i++) if(S[i] == winner) ANS.push(i); while(!ANS.empty()) { cout<<ANS.top()<<" "; ANS.pop(); } cout<<endl; } else { cout<<"NIE"<<endl; } return 0; } |