#include <iostream> #include <vector> #include <set> using namespace std; const int maxn = 200000; struct edge { edge(int dst, int dual): dest(dst), dualInd(dual) {} int dest; int dualInd; bool valid = true; }; vector<edge> graph[maxn+1]; int degree[maxn+1]; bool removed[maxn+1]; int bfsNum[maxn+1]; //first - stopien wierzcholka //second - numer wierzcholka set<pair<int, int> > spii; int n,m,d,a,b; int bfs(int s, int nr) { int size = 0; vector<int> q; q.push_back(s); bfsNum[s] = nr; for(int i=0;i<q.size();i++) { size++; for(vector<edge>::iterator it2 = graph[q[i]].begin();it2 != graph[q[i]].end();it2++) { if(it2->valid && !bfsNum[it2->dest]) { q.push_back(it2->dest); bfsNum[it2->dest] = nr; } } } return size; } void removeVerticesWithLowerDegree() { for(int i=1;i<=n;i++) spii.insert(make_pair(degree[i],i)); while(spii.size() > 0) { pair<int,int> pii = *spii.begin(); spii.erase(spii.begin()); if(removed[pii.second]) continue; if(pii.first >= d) break; removed[pii.second] = true; for(vector<edge>::iterator it = graph[pii.second].begin(); it != graph[pii.second].end();it++) { degree[it->dest]--; spii.insert(make_pair(degree[it->dest], it->dest)); it->valid = false; graph[it->dest][it->dualInd].valid = false; } } } int main() { cin >> n >> m >> d; for(int i=0;i<m;i++) { cin >> a >> b; graph[a].push_back(edge(b, graph[b].size())); graph[b].push_back(edge(a, graph[a].size()-1)); degree[a]++; degree[b]++; } removeVerticesWithLowerDegree(); int num = 0; int maxSize = 0; int maxSizeNr; for(int s=1;s<=n;s++) if(!removed[s] && !bfsNum[s]) { int size = bfs(s, ++num); if(size > maxSize) { maxSize = size; maxSizeNr = num; } } if(maxSize == 0) cout << "NIE\n"; else { cout << maxSize << '\n'; for(int i=1;i<=n;i++) if(bfsNum[i] == maxSizeNr) cout << i << ' '; cout << '\n'; } 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 | #include <iostream> #include <vector> #include <set> using namespace std; const int maxn = 200000; struct edge { edge(int dst, int dual): dest(dst), dualInd(dual) {} int dest; int dualInd; bool valid = true; }; vector<edge> graph[maxn+1]; int degree[maxn+1]; bool removed[maxn+1]; int bfsNum[maxn+1]; //first - stopien wierzcholka //second - numer wierzcholka set<pair<int, int> > spii; int n,m,d,a,b; int bfs(int s, int nr) { int size = 0; vector<int> q; q.push_back(s); bfsNum[s] = nr; for(int i=0;i<q.size();i++) { size++; for(vector<edge>::iterator it2 = graph[q[i]].begin();it2 != graph[q[i]].end();it2++) { if(it2->valid && !bfsNum[it2->dest]) { q.push_back(it2->dest); bfsNum[it2->dest] = nr; } } } return size; } void removeVerticesWithLowerDegree() { for(int i=1;i<=n;i++) spii.insert(make_pair(degree[i],i)); while(spii.size() > 0) { pair<int,int> pii = *spii.begin(); spii.erase(spii.begin()); if(removed[pii.second]) continue; if(pii.first >= d) break; removed[pii.second] = true; for(vector<edge>::iterator it = graph[pii.second].begin(); it != graph[pii.second].end();it++) { degree[it->dest]--; spii.insert(make_pair(degree[it->dest], it->dest)); it->valid = false; graph[it->dest][it->dualInd].valid = false; } } } int main() { cin >> n >> m >> d; for(int i=0;i<m;i++) { cin >> a >> b; graph[a].push_back(edge(b, graph[b].size())); graph[b].push_back(edge(a, graph[a].size()-1)); degree[a]++; degree[b]++; } removeVerticesWithLowerDegree(); int num = 0; int maxSize = 0; int maxSizeNr; for(int s=1;s<=n;s++) if(!removed[s] && !bfsNum[s]) { int size = bfs(s, ++num); if(size > maxSize) { maxSize = size; maxSizeNr = num; } } if(maxSize == 0) cout << "NIE\n"; else { cout << maxSize << '\n'; for(int i=1;i<=n;i++) if(bfsNum[i] == maxSizeNr) cout << i << ' '; cout << '\n'; } return 0; } |