#include <iostream> #include <vector> #include <queue> #include <algorithm> using namespace std; vector<vector<int> > graph; vector<bool> s; vector<int> solution; vector<int> temp; int maximum; int dfs(int x) { if(s[x]) { int counter=1; s[x] = 0; temp.push_back(x); for(int i=0; i<graph[x].size(); ++i) { counter += dfs(graph[x][i]); } return counter; } else return 0; } int main() { //początek dobrze wszystko int n, m, d; int maximum=0; int counter; cin >> n >> m >> d; graph.resize(n); vector<int> deg(n,0); s.clear(); s.resize(n,1); queue<int> q; int x, y; for(int i=0; i<m; ++i) { cin >> x >> y; --x; --y; graph[x].push_back(y); graph[y].push_back(x); deg[x]++; deg[y]++; } for(int i=0; i<n; ++i) { if(deg[i]<d) { s[i] = 0; q.push(i); } } while(!q.empty()) { x = q.front(); q.pop(); for(int i=0; i<graph[x].size(); ++i) { if(s[graph[x][i]]) { --deg[graph[x][i]]; if(deg[graph[x][i]]<d) { q.push(graph[x][i]); s[graph[x][i]] = 0; } } } } //koniec dobrze wszystko for(int i=0; i<n; ++i) { temp.clear(); x = dfs(i); if(x>maximum) { solution = temp; maximum = x; } } if(maximum!=0) { sort(solution.begin(), solution.end()); cout << maximum << endl; for(int i=0; i<solution.size(); ++i) cout << solution[i]+1 << " "; } else cout << "NIE"; 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 | #include <iostream> #include <vector> #include <queue> #include <algorithm> using namespace std; vector<vector<int> > graph; vector<bool> s; vector<int> solution; vector<int> temp; int maximum; int dfs(int x) { if(s[x]) { int counter=1; s[x] = 0; temp.push_back(x); for(int i=0; i<graph[x].size(); ++i) { counter += dfs(graph[x][i]); } return counter; } else return 0; } int main() { //początek dobrze wszystko int n, m, d; int maximum=0; int counter; cin >> n >> m >> d; graph.resize(n); vector<int> deg(n,0); s.clear(); s.resize(n,1); queue<int> q; int x, y; for(int i=0; i<m; ++i) { cin >> x >> y; --x; --y; graph[x].push_back(y); graph[y].push_back(x); deg[x]++; deg[y]++; } for(int i=0; i<n; ++i) { if(deg[i]<d) { s[i] = 0; q.push(i); } } while(!q.empty()) { x = q.front(); q.pop(); for(int i=0; i<graph[x].size(); ++i) { if(s[graph[x][i]]) { --deg[graph[x][i]]; if(deg[graph[x][i]]<d) { q.push(graph[x][i]); s[graph[x][i]] = 0; } } } } //koniec dobrze wszystko for(int i=0; i<n; ++i) { temp.clear(); x = dfs(i); if(x>maximum) { solution = temp; maximum = x; } } if(maximum!=0) { sort(solution.begin(), solution.end()); cout << maximum << endl; for(int i=0; i<solution.size(); ++i) cout << solution[i]+1 << " "; } else cout << "NIE"; return 0; } |