#include <iostream> #include <vector> #include <set> #include <map> #include <algorithm> using namespace std; #define REP(x,n) for(int x=0;x<(n);++x) #define VAR(x,n) __typeof(n) x = (n) #define FOREACH(x,n) for(VAR(x,(n).begin());x!=(n).end();++x) const int MAX_N = 200002; struct CNode : set<int> { bool visited; CNode() : visited(false) {} }; CNode graph[MAX_N]; struct comp { bool operator()(const int& a, const int& b) const { return graph[a].size() == graph[b].size() ? a < b : graph[a].size() < graph[b].size(); } }; int lista[MAX_N]; void bfs(int begin, set<int, comp>& V, set<int>& wyn) { int b,e; lista[b=e=0] = begin; graph[begin].visited = true; while(b<=e) { int elem = lista[b++]; wyn.insert(elem); V.erase(elem); FOREACH(it, graph[elem]) if(!graph[*it].visited) { graph[*it].visited = true; lista[++e] = *it; } } } void dfs(int current, set<int, comp>& V, set<int>& wyn) { wyn.insert(current); V.erase(current); graph[current].visited = true; FOREACH(it, graph[current]) { if (!graph[*it].visited) dfs(*it, V, wyn); } } int main() { ios_base::sync_with_stdio(0); int n, m, d, a, b; cin >> n >> m >> d; // scanf("%d %d %d", &n, &m, &d); REP(x, m) { // scanf("%d %d", &a, &b); cin >> a >> b; graph[--a].insert(--b); graph[b].insert(a); } set<int, comp> wierzch; REP(x, n) wierzch.insert(x); while (wierzch.size()) { int v = *wierzch.begin(); if (graph[v].size() >= d) break; wierzch.erase(v); // if( !(wierzch.size() & 1023)) { // printf("delete %d - %d neighbours; %d left\n", v+1, graph[v].size(), wierzch.size()); // map<int,int> rozmiary; // REP(x,n) // rozmiary[graph[x].size()]++; // FOREACH(it, rozmiary) // printf("%d:: %d; ", it->first, it->second); // printf("\n"); // } FOREACH(it, graph[v]) { wierzch.erase(*it); graph[*it].erase(v); wierzch.insert(*it); } graph[v].clear(); } set<int> wyn; // printf("%d left\n", wierzch.size()); while (wierzch.size()) { set<int> curWyn; dfs(*wierzch.begin(), wierzch, curWyn); if (curWyn.size() > wyn.size()) wyn = curWyn; // printf("BFS: %d wyn; left %d\n", curWyn.size(), wierzch.size()); } if (wyn.size()) { // printf("%d\n", wyn.size()); cout << wyn.size() << endl; FOREACH(it, wyn) cout << (*it)+1 << " "; // printf("%d ", (*it) + 1); } else // puts("NIE"); cout << "NIE"; 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 | #include <iostream> #include <vector> #include <set> #include <map> #include <algorithm> using namespace std; #define REP(x,n) for(int x=0;x<(n);++x) #define VAR(x,n) __typeof(n) x = (n) #define FOREACH(x,n) for(VAR(x,(n).begin());x!=(n).end();++x) const int MAX_N = 200002; struct CNode : set<int> { bool visited; CNode() : visited(false) {} }; CNode graph[MAX_N]; struct comp { bool operator()(const int& a, const int& b) const { return graph[a].size() == graph[b].size() ? a < b : graph[a].size() < graph[b].size(); } }; int lista[MAX_N]; void bfs(int begin, set<int, comp>& V, set<int>& wyn) { int b,e; lista[b=e=0] = begin; graph[begin].visited = true; while(b<=e) { int elem = lista[b++]; wyn.insert(elem); V.erase(elem); FOREACH(it, graph[elem]) if(!graph[*it].visited) { graph[*it].visited = true; lista[++e] = *it; } } } void dfs(int current, set<int, comp>& V, set<int>& wyn) { wyn.insert(current); V.erase(current); graph[current].visited = true; FOREACH(it, graph[current]) { if (!graph[*it].visited) dfs(*it, V, wyn); } } int main() { ios_base::sync_with_stdio(0); int n, m, d, a, b; cin >> n >> m >> d; // scanf("%d %d %d", &n, &m, &d); REP(x, m) { // scanf("%d %d", &a, &b); cin >> a >> b; graph[--a].insert(--b); graph[b].insert(a); } set<int, comp> wierzch; REP(x, n) wierzch.insert(x); while (wierzch.size()) { int v = *wierzch.begin(); if (graph[v].size() >= d) break; wierzch.erase(v); // if( !(wierzch.size() & 1023)) { // printf("delete %d - %d neighbours; %d left\n", v+1, graph[v].size(), wierzch.size()); // map<int,int> rozmiary; // REP(x,n) // rozmiary[graph[x].size()]++; // FOREACH(it, rozmiary) // printf("%d:: %d; ", it->first, it->second); // printf("\n"); // } FOREACH(it, graph[v]) { wierzch.erase(*it); graph[*it].erase(v); wierzch.insert(*it); } graph[v].clear(); } set<int> wyn; // printf("%d left\n", wierzch.size()); while (wierzch.size()) { set<int> curWyn; dfs(*wierzch.begin(), wierzch, curWyn); if (curWyn.size() > wyn.size()) wyn = curWyn; // printf("BFS: %d wyn; left %d\n", curWyn.size(), wierzch.size()); } if (wyn.size()) { // printf("%d\n", wyn.size()); cout << wyn.size() << endl; FOREACH(it, wyn) cout << (*it)+1 << " "; // printf("%d ", (*it) + 1); } else // puts("NIE"); cout << "NIE"; return 0; } |