#include <iostream> #include <vector> #include <algorithm> #include <utility> #include <set> #include <queue> using namespace std; #define int long long struct node{ int spojne=-1; set<int> edge; }; void dfs(int s,vector<node> &G,int licznik){ G[s].spojne=licznik; for(auto &i:G[s].edge){ if(G[i].spojne==-1) dfs(i,G,licznik); } } main(){ ios_base::sync_with_stdio(false); int n,m,d; cin >> n >> m >> d; vector<node> G(n+1); vector<int> T(n+1,0); vector<pair<int,int> > Input; for(int i=0;i<m;i++){ int u,v; cin >> u >> v; G[u].edge.insert(v); G[v].edge.insert(u); } queue<int> Q; for(int i=1;i<=n;i++){ if(G[i].edge.size()<d){ Q.push(i); } } while(!Q.empty()){ int u=Q.front(); Q.pop(); for(auto &i:G[u].edge){ G[i].edge.erase(u); if(G[i].edge.size()<d) Q.push(i); } G[u].edge.clear(); } int licznik=0; for(int i=1;i<=n;i++){ //cout << G[i].edge.size() << endl; if(G[i].spojne==-1){ dfs(i,G,licznik++); } } //cout << licznik << endl; vector<vector<int> > Spojne(licznik); for(int i=1;i<=n;i++){ Spojne[G[i].spojne].push_back(i); } int numer=0; for(int i=1;i<licznik;i++){ if(Spojne[i].size()>Spojne[numer].size()) numer=i; } sort(Spojne[numer].begin(),Spojne[numer].end()); if(Spojne[numer].size()==1) cout << "NIE"<< endl; else{ cout << Spojne[numer].size() << endl; for(auto &i:Spojne[numer]) cout << 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 | #include <iostream> #include <vector> #include <algorithm> #include <utility> #include <set> #include <queue> using namespace std; #define int long long struct node{ int spojne=-1; set<int> edge; }; void dfs(int s,vector<node> &G,int licznik){ G[s].spojne=licznik; for(auto &i:G[s].edge){ if(G[i].spojne==-1) dfs(i,G,licznik); } } main(){ ios_base::sync_with_stdio(false); int n,m,d; cin >> n >> m >> d; vector<node> G(n+1); vector<int> T(n+1,0); vector<pair<int,int> > Input; for(int i=0;i<m;i++){ int u,v; cin >> u >> v; G[u].edge.insert(v); G[v].edge.insert(u); } queue<int> Q; for(int i=1;i<=n;i++){ if(G[i].edge.size()<d){ Q.push(i); } } while(!Q.empty()){ int u=Q.front(); Q.pop(); for(auto &i:G[u].edge){ G[i].edge.erase(u); if(G[i].edge.size()<d) Q.push(i); } G[u].edge.clear(); } int licznik=0; for(int i=1;i<=n;i++){ //cout << G[i].edge.size() << endl; if(G[i].spojne==-1){ dfs(i,G,licznik++); } } //cout << licznik << endl; vector<vector<int> > Spojne(licznik); for(int i=1;i<=n;i++){ Spojne[G[i].spojne].push_back(i); } int numer=0; for(int i=1;i<licznik;i++){ if(Spojne[i].size()>Spojne[numer].size()) numer=i; } sort(Spojne[numer].begin(),Spojne[numer].end()); if(Spojne[numer].size()==1) cout << "NIE"<< endl; else{ cout << Spojne[numer].size() << endl; for(auto &i:Spojne[numer]) cout << i << ' '; cout << endl; } return 0; } |