#include <cstdio> #include <iostream> #include <algorithm> #include <string> #include <vector> #include <set> using namespace std; int n, m, d, a, b; vector<vector<int> > G; vector<int> degree; vector<int> parent; int find(int v) { if( parent[v]<0 ) return v; else return parent[v] = find(parent[v]); } void join(int u, int v) { u = find(u); v = find(v); if( u==v ) return; if( parent[u] < parent[v] ) { parent[u] += parent[v]; parent[v] = u; } else { parent[v] += parent[u]; parent[u] = v; } } struct cmp{ bool operator() (int i, int j) { if( degree[i]==degree[j] ) return i<j; else return degree[i]<degree[j]; } }; set<int,cmp> S; set<int,cmp>::iterator it; int main() { ios_base::sync_with_stdio(false); cin >> n >> m >> d; G.resize(n+1); degree.resize(n+1,0); for( int i=0 ; i<m ; i++ ) { cin >> a >> b; G[a].push_back(b); G[b].push_back(a); degree[a]++; degree[b]++; } for( int u=1 ; u<=n ; u++ ) S.insert(u); while( !S.empty() ) { it = S.begin(); if( degree[*it] < d ) { int u = *it; S.erase(it); degree[u] = -1; for( int i=0 ; i<G[u].size() ; i++ ) { if( degree[ G[u][i] ] < 0 ) continue; S.erase( G[u][i] ); degree[ G[u][i] ]--; S.insert( G[u][i] ); } } else break; } if( S.empty() ) { cout << "NIE" << endl; return 0; } parent.resize(n+1,-1); for( int u=1 ; u<=n ; u++ ) { if( degree[u]>=d ) { for( int i=0 ; i<G[u].size() ; i++ ) { if( degree[ G[u][i] ]>=d ) join( u, G[u][i] ); } } } int biggest = 0; parent[biggest] = 0; for( int u=1 ; u<=n ; u++ ) if( degree[u]>=d && parent[u]<parent[biggest] ) biggest = u; cout << (-parent[biggest]) << endl; for( int u=1 ; u<=n ; u++ ) if( find(u)==biggest ) cout << u << " "; 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 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 | #include <cstdio> #include <iostream> #include <algorithm> #include <string> #include <vector> #include <set> using namespace std; int n, m, d, a, b; vector<vector<int> > G; vector<int> degree; vector<int> parent; int find(int v) { if( parent[v]<0 ) return v; else return parent[v] = find(parent[v]); } void join(int u, int v) { u = find(u); v = find(v); if( u==v ) return; if( parent[u] < parent[v] ) { parent[u] += parent[v]; parent[v] = u; } else { parent[v] += parent[u]; parent[u] = v; } } struct cmp{ bool operator() (int i, int j) { if( degree[i]==degree[j] ) return i<j; else return degree[i]<degree[j]; } }; set<int,cmp> S; set<int,cmp>::iterator it; int main() { ios_base::sync_with_stdio(false); cin >> n >> m >> d; G.resize(n+1); degree.resize(n+1,0); for( int i=0 ; i<m ; i++ ) { cin >> a >> b; G[a].push_back(b); G[b].push_back(a); degree[a]++; degree[b]++; } for( int u=1 ; u<=n ; u++ ) S.insert(u); while( !S.empty() ) { it = S.begin(); if( degree[*it] < d ) { int u = *it; S.erase(it); degree[u] = -1; for( int i=0 ; i<G[u].size() ; i++ ) { if( degree[ G[u][i] ] < 0 ) continue; S.erase( G[u][i] ); degree[ G[u][i] ]--; S.insert( G[u][i] ); } } else break; } if( S.empty() ) { cout << "NIE" << endl; return 0; } parent.resize(n+1,-1); for( int u=1 ; u<=n ; u++ ) { if( degree[u]>=d ) { for( int i=0 ; i<G[u].size() ; i++ ) { if( degree[ G[u][i] ]>=d ) join( u, G[u][i] ); } } } int biggest = 0; parent[biggest] = 0; for( int u=1 ; u<=n ; u++ ) if( degree[u]>=d && parent[u]<parent[biggest] ) biggest = u; cout << (-parent[biggest]) << endl; for( int u=1 ; u<=n ; u++ ) if( find(u)==biggest ) cout << u << " "; cout << endl; return 0; } |