#include <cstdio> #include <vector> #include <set> #include <queue> #include <algorithm> #pragma warning (disable : 4996) using namespace std; int main(int argc, char* argv[]) { int N, M; unsigned D; scanf("%d %d %ud", &N, &M, &D); vector<set<int> > graph(N+1); for(int k=0; k<M; k++) { int u, v; scanf("%d %d", &u, &v); graph[u].insert(v); graph[v].insert(u); } queue<int> qqq; for(int v=1; v<=N; v++) { if(graph[v].size() < D) qqq.push(v); } while(!qqq.empty()) { int u = qqq.front(); qqq.pop(); for(set<int>::iterator w = graph[u].begin(); w != graph[u].end(); w++) { if(graph[*w].size() == D && graph[*w].find(u) != graph[*w].end() && *w != u) { qqq.push(*w); } graph[*w].erase(u); } graph[u].clear(); } vector<int> what_component(N+1, -1); vector<int> components_sizes; for(int v=1; v<=N; v++) { if(graph[v].size() >= D && what_component[v] == -1) { components_sizes.push_back(1); what_component[v] = (int)components_sizes.size() -1; qqq.push(v); while(!qqq.empty()) { int curr = qqq.front(); qqq.pop(); for(set<int>::iterator next = graph[curr].begin(); next != graph[curr].end(); next++) { if(what_component[*next] == -1) { what_component[*next] = (int)components_sizes.size() -1; components_sizes.back()++; qqq.push(*next); } } } } } if(components_sizes.empty()) { printf("NIE\n"); } else { int max_component_code = max_element(components_sizes.begin(), components_sizes.end()) - components_sizes.begin(); printf("%d\n", components_sizes[max_component_code]); bool is_1st = true; for(int v=1; v<=N; v++) { if(what_component[v] == max_component_code) { if(is_1st) is_1st = false; else printf(" "); printf("%d", v); } } printf("\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 | #include <cstdio> #include <vector> #include <set> #include <queue> #include <algorithm> #pragma warning (disable : 4996) using namespace std; int main(int argc, char* argv[]) { int N, M; unsigned D; scanf("%d %d %ud", &N, &M, &D); vector<set<int> > graph(N+1); for(int k=0; k<M; k++) { int u, v; scanf("%d %d", &u, &v); graph[u].insert(v); graph[v].insert(u); } queue<int> qqq; for(int v=1; v<=N; v++) { if(graph[v].size() < D) qqq.push(v); } while(!qqq.empty()) { int u = qqq.front(); qqq.pop(); for(set<int>::iterator w = graph[u].begin(); w != graph[u].end(); w++) { if(graph[*w].size() == D && graph[*w].find(u) != graph[*w].end() && *w != u) { qqq.push(*w); } graph[*w].erase(u); } graph[u].clear(); } vector<int> what_component(N+1, -1); vector<int> components_sizes; for(int v=1; v<=N; v++) { if(graph[v].size() >= D && what_component[v] == -1) { components_sizes.push_back(1); what_component[v] = (int)components_sizes.size() -1; qqq.push(v); while(!qqq.empty()) { int curr = qqq.front(); qqq.pop(); for(set<int>::iterator next = graph[curr].begin(); next != graph[curr].end(); next++) { if(what_component[*next] == -1) { what_component[*next] = (int)components_sizes.size() -1; components_sizes.back()++; qqq.push(*next); } } } } } if(components_sizes.empty()) { printf("NIE\n"); } else { int max_component_code = max_element(components_sizes.begin(), components_sizes.end()) - components_sizes.begin(); printf("%d\n", components_sizes[max_component_code]); bool is_1st = true; for(int v=1; v<=N; v++) { if(what_component[v] == max_component_code) { if(is_1st) is_1st = false; else printf(" "); printf("%d", v); } } printf("\n"); } return 0; } |