#include <iostream> #include <vector> #include <queue> #include <algorithm> using namespace std; const int MAXN = 200010; vector <int> v[MAXN]; vector <int> tmp[MAXN]; bool met[MAXN], burned[MAXN]; int deg[MAXN]; int d; bool dfs(int n, int start) { met[n] = true; tmp[start].push_back(n); for(int i = 0; i < v[n].size(); ++i) { if(!met[v[n][i]] and !burned[v[n][i]]) { met[v[n][i]] = true; dfs(v[n][i], start); } } } int main() { ios_base::sync_with_stdio(false); int n, m; cin >> n >> m >> d; queue <int> q; for(int i = 0; i < m; ++i) { int a, b; cin >> a >> b; v[a].push_back(b); v[b].push_back(a); } for(int i = 1; i <= n; ++i) { deg[i] = v[i].size(); } for(int i = 1; i <= n; ++i) { if(deg[i] < d) { burned[i] = true; q.push(i); } } while(!q.empty()) { int k = q.front(); q.pop(); for(int j = 0; j < v[k].size(); ++j) { deg[v[k][j]] -= 1; if(deg[v[k][j]] < d and !burned[v[k][j]]) { burned[v[k][j]] = true; q.push(v[k][j]); } } } int res = 0, ind; for(int i = 1; i <= n; ++i) { if(!burned[i]) { dfs(i, i); } if(tmp[i].size() > 1 and tmp[i].size() > res) { ind = i; res = tmp[i].size(); } } if(res < 2) cout << "NIE" << endl; else { cout << tmp[ind].size() << endl; sort(tmp[ind].begin(), tmp[ind].end()); for(int i = 0; i < tmp[ind].size(); ++i) { cout << tmp[ind][i] << " "; } cout << 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 | #include <iostream> #include <vector> #include <queue> #include <algorithm> using namespace std; const int MAXN = 200010; vector <int> v[MAXN]; vector <int> tmp[MAXN]; bool met[MAXN], burned[MAXN]; int deg[MAXN]; int d; bool dfs(int n, int start) { met[n] = true; tmp[start].push_back(n); for(int i = 0; i < v[n].size(); ++i) { if(!met[v[n][i]] and !burned[v[n][i]]) { met[v[n][i]] = true; dfs(v[n][i], start); } } } int main() { ios_base::sync_with_stdio(false); int n, m; cin >> n >> m >> d; queue <int> q; for(int i = 0; i < m; ++i) { int a, b; cin >> a >> b; v[a].push_back(b); v[b].push_back(a); } for(int i = 1; i <= n; ++i) { deg[i] = v[i].size(); } for(int i = 1; i <= n; ++i) { if(deg[i] < d) { burned[i] = true; q.push(i); } } while(!q.empty()) { int k = q.front(); q.pop(); for(int j = 0; j < v[k].size(); ++j) { deg[v[k][j]] -= 1; if(deg[v[k][j]] < d and !burned[v[k][j]]) { burned[v[k][j]] = true; q.push(v[k][j]); } } } int res = 0, ind; for(int i = 1; i <= n; ++i) { if(!burned[i]) { dfs(i, i); } if(tmp[i].size() > 1 and tmp[i].size() > res) { ind = i; res = tmp[i].size(); } } if(res < 2) cout << "NIE" << endl; else { cout << tmp[ind].size() << endl; sort(tmp[ind].begin(), tmp[ind].end()); for(int i = 0; i < tmp[ind].size(); ++i) { cout << tmp[ind][i] << " "; } cout << endl; } return 0; } |