#include <cstdio> #include <algorithm> #include <vector> #include <queue> using namespace std; queue<int> q; vector<vector<int> > v; vector<int> vecDegree; vector<bool> visited; vector<int> vResult; vector<bool> vOutOf; int n, m, d; int ctr=0, bestResult=0, bestIdx=0; void dfs(int x){ ctr++; visited[x]=true; for(int i = 0; i < v[x].size(); i++){ if(!visited[v[x][i]] && vecDegree[v[x][i]] >= d){ dfs(v[x][i]); } } } void dfs2(int x){ visited[x]=true; vResult.push_back(x); for(int i = 0; i < v[x].size(); i++){ if(!visited[v[x][i]] && vecDegree[v[x][i]] >= d){ dfs2(v[x][i]); } } } int main(){ scanf("%d%d%d", &n, &m, &d); v.resize(n); vecDegree.resize(n); visited.resize(n); vOutOf.resize(n); for(int i = 0; i < m; i++){ int a, b; scanf("%d%d", &a, &b); a--; b--; v[a].push_back(b); v[b].push_back(a); vecDegree[a]++; vecDegree[b]++; } for(int i = 0; i < n; i++){ if(v[i].size() < d){ q.push(i); } } while(!q.empty()){ int x = q.front(); q.pop(); if(vOutOf[x]==true)continue; vecDegree[x]=0; vOutOf[x]=true; for(int i = 0; i < v[x].size(); i++){ /*if(vecDegree[v[x][i]] > 0){ vecDegree[v[x][i]]--; if(vecDegree[v[x][i]] < d){ q.push(v[x][i]); vecDegree[v[x][i]]=0; } }*/ vecDegree[v[x][i]]--; if(!vOutOf[v[x][i]] && vecDegree[v[x][i]] < d){ q.push(v[x][i]); vecDegree[v[x][i]]=0; } } } for(int i = 0; i < n; i++){ if(vecDegree[i] >= d){ ctr=0; dfs(i); if(ctr > bestResult){ bestResult=ctr; bestIdx=i; } } } if(bestResult==0){ printf("NIE\n"); return 0; } for(int i = 0; i < n; i++){ visited[i]=false; } dfs2(bestIdx); sort(vResult.begin(), vResult.end()); printf("%d\n", bestResult); for(int i = 0; i < vResult.size(); i++){ printf("%d ", vResult[i]+1); } }
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 | #include <cstdio> #include <algorithm> #include <vector> #include <queue> using namespace std; queue<int> q; vector<vector<int> > v; vector<int> vecDegree; vector<bool> visited; vector<int> vResult; vector<bool> vOutOf; int n, m, d; int ctr=0, bestResult=0, bestIdx=0; void dfs(int x){ ctr++; visited[x]=true; for(int i = 0; i < v[x].size(); i++){ if(!visited[v[x][i]] && vecDegree[v[x][i]] >= d){ dfs(v[x][i]); } } } void dfs2(int x){ visited[x]=true; vResult.push_back(x); for(int i = 0; i < v[x].size(); i++){ if(!visited[v[x][i]] && vecDegree[v[x][i]] >= d){ dfs2(v[x][i]); } } } int main(){ scanf("%d%d%d", &n, &m, &d); v.resize(n); vecDegree.resize(n); visited.resize(n); vOutOf.resize(n); for(int i = 0; i < m; i++){ int a, b; scanf("%d%d", &a, &b); a--; b--; v[a].push_back(b); v[b].push_back(a); vecDegree[a]++; vecDegree[b]++; } for(int i = 0; i < n; i++){ if(v[i].size() < d){ q.push(i); } } while(!q.empty()){ int x = q.front(); q.pop(); if(vOutOf[x]==true)continue; vecDegree[x]=0; vOutOf[x]=true; for(int i = 0; i < v[x].size(); i++){ /*if(vecDegree[v[x][i]] > 0){ vecDegree[v[x][i]]--; if(vecDegree[v[x][i]] < d){ q.push(v[x][i]); vecDegree[v[x][i]]=0; } }*/ vecDegree[v[x][i]]--; if(!vOutOf[v[x][i]] && vecDegree[v[x][i]] < d){ q.push(v[x][i]); vecDegree[v[x][i]]=0; } } } for(int i = 0; i < n; i++){ if(vecDegree[i] >= d){ ctr=0; dfs(i); if(ctr > bestResult){ bestResult=ctr; bestIdx=i; } } } if(bestResult==0){ printf("NIE\n"); return 0; } for(int i = 0; i < n; i++){ visited[i]=false; } dfs2(bestIdx); sort(vResult.begin(), vResult.end()); printf("%d\n", bestResult); for(int i = 0; i < vResult.size(); i++){ printf("%d ", vResult[i]+1); } } |