#include <cstdio> #include <list> #include <algorithm> #define DEBUG #ifdef DEBUG #undef DEBUG #endif using namespace std; long long n, m, d; long long a, b; #define MAX_N 200001 typedef list<long long> type_G; type_G G[MAX_N]; long long Conn[MAX_N]; bool Invalid[MAX_N]; bool Grouped[MAX_N]; long long GroupSize[MAX_N]; type_G Groups[MAX_N]; void CheckCity(long long index) { type_G::iterator it; /* Do not invalidate already invalidated city */ if (Invalid[index]) return; if (Conn[index] < d) { Invalid[index] = true; /* Remove 1 from all cities that we were connected to */ for (it=G[index].begin(); it!=G[index].end(); it++) { Conn[*it]--; } /* Check all connected cities if they are still valid */ for (it=G[index].begin(); it!=G[index].end(); it++) { /* Check once again only cities that have already been checked */ if (*it < index) { /* * We do new check of city only once for every connection that * it has, so there are maximum m additional checks */ CheckCity(*it); } } } } void AssignGroup(long long index, long long group_index) { type_G::iterator it; Grouped[index] = true; Groups[group_index].push_back(index); GroupSize[group_index]++; for (it=G[index].begin(); it!=G[index].end(); it++) { if ( (!Invalid[*it]) && (Grouped[*it]==0) ) { AssignGroup(*it, group_index); } } } void GroupCities() { long long i; type_G::iterator it; long long group_id = 0; for (i=0; i<n; i++) { if ( (!Invalid[i]) && (!Grouped[i])) { AssignGroup(i, group_id); group_id++; } } } int main() { long long i; long long max_group_index = 0; scanf("%lld%lld%lld", &n, &m, &d); for (i=0; i<m; i++) { scanf("%lld%lld", &a, &b); G[a].push_back(b); G[b].push_back(a); Conn[a]++; Conn[b]++; } /* Check all cities if they have >= d connections */ for (i=0; i<n; i++) { CheckCity(i); } /* Group cities */ GroupCities(); #ifdef DEBUG printf("Printing Groups begin\n"); for (i=0; GroupSize[i]>0; i++) { printf("Group[%lld]:", i); type_G::iterator it; for (it=Groups[i].begin(); it!=Groups[i].end(); it++) { printf(" %lld", *it); } printf("\n"); } printf("Printing Groups end\n\n"); #endif /* Find maximum sized group */ for (i=1; GroupSize[i]>0; i++) { if (GroupSize[i] > GroupSize[max_group_index]) { max_group_index = i; } } /* Check if there is at least one group */ if (GroupSize[max_group_index] == 0) { printf("NIE\n"); return 0; } /* Print all members of this group */ type_G::iterator it; Groups[max_group_index].sort(); it = Groups[max_group_index].begin(); printf("%lld\n", GroupSize[max_group_index]); printf("%lld", *it); it++; for (; it != Groups[max_group_index].end(); it++) { printf(" %lld", *it); } printf("\n"); }
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 | #include <cstdio> #include <list> #include <algorithm> #define DEBUG #ifdef DEBUG #undef DEBUG #endif using namespace std; long long n, m, d; long long a, b; #define MAX_N 200001 typedef list<long long> type_G; type_G G[MAX_N]; long long Conn[MAX_N]; bool Invalid[MAX_N]; bool Grouped[MAX_N]; long long GroupSize[MAX_N]; type_G Groups[MAX_N]; void CheckCity(long long index) { type_G::iterator it; /* Do not invalidate already invalidated city */ if (Invalid[index]) return; if (Conn[index] < d) { Invalid[index] = true; /* Remove 1 from all cities that we were connected to */ for (it=G[index].begin(); it!=G[index].end(); it++) { Conn[*it]--; } /* Check all connected cities if they are still valid */ for (it=G[index].begin(); it!=G[index].end(); it++) { /* Check once again only cities that have already been checked */ if (*it < index) { /* * We do new check of city only once for every connection that * it has, so there are maximum m additional checks */ CheckCity(*it); } } } } void AssignGroup(long long index, long long group_index) { type_G::iterator it; Grouped[index] = true; Groups[group_index].push_back(index); GroupSize[group_index]++; for (it=G[index].begin(); it!=G[index].end(); it++) { if ( (!Invalid[*it]) && (Grouped[*it]==0) ) { AssignGroup(*it, group_index); } } } void GroupCities() { long long i; type_G::iterator it; long long group_id = 0; for (i=0; i<n; i++) { if ( (!Invalid[i]) && (!Grouped[i])) { AssignGroup(i, group_id); group_id++; } } } int main() { long long i; long long max_group_index = 0; scanf("%lld%lld%lld", &n, &m, &d); for (i=0; i<m; i++) { scanf("%lld%lld", &a, &b); G[a].push_back(b); G[b].push_back(a); Conn[a]++; Conn[b]++; } /* Check all cities if they have >= d connections */ for (i=0; i<n; i++) { CheckCity(i); } /* Group cities */ GroupCities(); #ifdef DEBUG printf("Printing Groups begin\n"); for (i=0; GroupSize[i]>0; i++) { printf("Group[%lld]:", i); type_G::iterator it; for (it=Groups[i].begin(); it!=Groups[i].end(); it++) { printf(" %lld", *it); } printf("\n"); } printf("Printing Groups end\n\n"); #endif /* Find maximum sized group */ for (i=1; GroupSize[i]>0; i++) { if (GroupSize[i] > GroupSize[max_group_index]) { max_group_index = i; } } /* Check if there is at least one group */ if (GroupSize[max_group_index] == 0) { printf("NIE\n"); return 0; } /* Print all members of this group */ type_G::iterator it; Groups[max_group_index].sort(); it = Groups[max_group_index].begin(); printf("%lld\n", GroupSize[max_group_index]); printf("%lld", *it); it++; for (; it != Groups[max_group_index].end(); it++) { printf(" %lld", *it); } printf("\n"); } |