#include <iostream> #include <vector> #include <bitset> #include <string> #include <iomanip> #include <map> #include <cmath> #include <utility> #include <cstdio> #include <stack> #include <algorithm> #include <cstring> #include <queue> #include <sstream> #include <set> #include <unordered_map> using namespace std; typedef pair<int,int> ii; typedef vector<int> vi; typedef vector<ii> vii; int N,M,d,a,b,dfsCNT; vector<vi> Adj,G; vector <bool> Skasowany; vi degree; vi dfs_num; vi lista_skasowanych; vi liko; void dfs_kasujacy(int u) { Skasowany[u]=true; // cout<<u<<" "; lista_skasowanych.push_back(u); for (int i=0;i<Adj[u].size();i++) { int v=Adj[u][i]; degree[v]--; if (degree[v]<d && !Skasowany[v]) dfs_kasujacy(v); } } void dfs(int u) { dfs_num[u]=dfsCNT; liko[dfsCNT]++; for (int i=0;i<G[u].size();i++) { int v=G[u][i]; if (dfs_num[v]==0) dfs(v); } } int main() { ios_base::sync_with_stdio(0); cin>>N>>M>>d; Adj.assign(N+2,vi()); Skasowany.assign(N+2,false); degree.assign(N+2,0); for (int i=0;i<M;i++) {cin>>a>>b; Adj[a].push_back(b); Adj[b].push_back(a); degree[a]++; degree[b]++;} for (int i=1;i<=N;i++) if (!Skasowany[i] && degree[i]<d) dfs_kasujacy(i); /* for (int i=1;i<=N;i++) cout<<"\ndegree "<<i<<" = "<<degree[i]<<" skasowany: "<<Skasowany[i]; */ G.assign(N+2,vi()); for (int i=1;i<=N;i++) { if (Skasowany[i]) continue; for (int j=0;j<Adj[i].size();j++) { int ver=Adj[i][j]; if (!Skasowany[ver]) { G[i].push_back(ver); } } } /* for (int i=1;i<=N;i++) { if (G[i].size()!=0) { cout<<"\n "<<i<<" "; for (int j=0;j<G[i].size();j++) { cout<<G[i][j]<<" "; } } } */ dfsCNT=1; dfs_num.assign(N+2,0); liko.assign(N+2,0); for (int i=1;i<=N;i++) { if (dfs_num[i]==0) { dfs(i); dfsCNT++; } } int max_size=-1,best_komp; for (int i=1;i<=dfsCNT;i++) { if (max_size<liko[i]) { max_size=liko[i]; best_komp=i; } } vi ans; for (int i=1;i<=N;i++) { if (dfs_num[i]==best_komp) ans.push_back(i); } sort(ans.begin(),ans.end()); if (max_size<2) cout<<"NIE"; else { cout<<max_size<<"\n"; for (int i=0;i<ans.size();i++) cout<<ans[i]<<" "; } 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 129 130 131 132 133 134 135 136 | #include <iostream> #include <vector> #include <bitset> #include <string> #include <iomanip> #include <map> #include <cmath> #include <utility> #include <cstdio> #include <stack> #include <algorithm> #include <cstring> #include <queue> #include <sstream> #include <set> #include <unordered_map> using namespace std; typedef pair<int,int> ii; typedef vector<int> vi; typedef vector<ii> vii; int N,M,d,a,b,dfsCNT; vector<vi> Adj,G; vector <bool> Skasowany; vi degree; vi dfs_num; vi lista_skasowanych; vi liko; void dfs_kasujacy(int u) { Skasowany[u]=true; // cout<<u<<" "; lista_skasowanych.push_back(u); for (int i=0;i<Adj[u].size();i++) { int v=Adj[u][i]; degree[v]--; if (degree[v]<d && !Skasowany[v]) dfs_kasujacy(v); } } void dfs(int u) { dfs_num[u]=dfsCNT; liko[dfsCNT]++; for (int i=0;i<G[u].size();i++) { int v=G[u][i]; if (dfs_num[v]==0) dfs(v); } } int main() { ios_base::sync_with_stdio(0); cin>>N>>M>>d; Adj.assign(N+2,vi()); Skasowany.assign(N+2,false); degree.assign(N+2,0); for (int i=0;i<M;i++) {cin>>a>>b; Adj[a].push_back(b); Adj[b].push_back(a); degree[a]++; degree[b]++;} for (int i=1;i<=N;i++) if (!Skasowany[i] && degree[i]<d) dfs_kasujacy(i); /* for (int i=1;i<=N;i++) cout<<"\ndegree "<<i<<" = "<<degree[i]<<" skasowany: "<<Skasowany[i]; */ G.assign(N+2,vi()); for (int i=1;i<=N;i++) { if (Skasowany[i]) continue; for (int j=0;j<Adj[i].size();j++) { int ver=Adj[i][j]; if (!Skasowany[ver]) { G[i].push_back(ver); } } } /* for (int i=1;i<=N;i++) { if (G[i].size()!=0) { cout<<"\n "<<i<<" "; for (int j=0;j<G[i].size();j++) { cout<<G[i][j]<<" "; } } } */ dfsCNT=1; dfs_num.assign(N+2,0); liko.assign(N+2,0); for (int i=1;i<=N;i++) { if (dfs_num[i]==0) { dfs(i); dfsCNT++; } } int max_size=-1,best_komp; for (int i=1;i<=dfsCNT;i++) { if (max_size<liko[i]) { max_size=liko[i]; best_komp=i; } } vi ans; for (int i=1;i<=N;i++) { if (dfs_num[i]==best_komp) ans.push_back(i); } sort(ans.begin(),ans.end()); if (max_size<2) cout<<"NIE"; else { cout<<max_size<<"\n"; for (int i=0;i<ans.size();i++) cout<<ans[i]<<" "; } return 0; } |