#include <cstdio> #include <set> #include <vector> #include <stack> using namespace std; struct Edge { int to; set<Edge*>::iterator rev; Edge(int _to) : to(_to) {} void set(set<Edge*>::iterator &r) { rev = r; } }; struct Vertex { int n; int c; bool erased; set<Edge*> e; Vertex(int _n):n(_n), c(0), erased(false) {} }; struct Graph { vector<Vertex*> g; set<Vertex*> s; Graph(int _n) { for (int i=0;i<_n;++i) { Vertex* v = new Vertex(i); g.push_back(v); s.insert(v); } } void add(int a, int b) { set<Edge*>::iterator itA, itB; Edge* inA = new Edge(b-1); Edge* inB = new Edge(a-1); itA = g[a-1]->e.insert(inA).first; itB = g[b-1]->e.insert(inB).first; inA->set(itB); inB->set(itA); } }; int main() { int n, m, d, a, b; scanf("%d%d%d",&n,&m,&d); Graph g(n); for (int i=0;i<m;++i) { scanf("%d%d",&a,&b); g.add(a, b); } bool again; do { again = false; set<Vertex*>::iterator it = g.s.begin(); while(it != g.s.end()) { Vertex* v = *it; if ((int)v->e.size()<d) { again = true; v->erased = true; g.s.erase(it++); for (set<Edge*>::iterator eit=v->e.begin(); eit!=v->e.end(); ++eit) { Edge *e = *eit; g.g[e->to]->e.erase(e->rev); } v->e.clear(); } else { ++it; } } } while(again); // --- spojne int color = 0; int size = 0; int max_color = 0; int max_size = 0; stack<int> stos; for (set<Vertex*>::iterator it = g.s.begin(); it!=g.s.end(); ++it) { if ((*it)->erased==false && (*it)->c==0) { ++color; size = 0; stos.push((*it)->n); while (!stos.empty()) { int v = stos.top(); stos.pop(); Vertex* ve = g.g[v]; if (ve->erased==false && ve->c==0) { ++size; ve->c = color; for (set<Edge*>::iterator eit=ve->e.begin(); eit!=ve->e.end(); ++eit) { Vertex *vt = g.g[(*eit)->to]; if (vt->erased==false && vt->c==0) { stos.push(vt->n); } } } } if (size>max_size) { max_size = size; max_color = color; } } } // --- wynik if (max_size<2) { printf("NIE\n"); } else { printf("%d\n", max_size); for (set<Vertex*>::iterator it = g.s.begin(); it!=g.s.end(); ++it) { if (max_color == (*it)->c) { printf("%d ", 1+(*it)->n); } } 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 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 | #include <cstdio> #include <set> #include <vector> #include <stack> using namespace std; struct Edge { int to; set<Edge*>::iterator rev; Edge(int _to) : to(_to) {} void set(set<Edge*>::iterator &r) { rev = r; } }; struct Vertex { int n; int c; bool erased; set<Edge*> e; Vertex(int _n):n(_n), c(0), erased(false) {} }; struct Graph { vector<Vertex*> g; set<Vertex*> s; Graph(int _n) { for (int i=0;i<_n;++i) { Vertex* v = new Vertex(i); g.push_back(v); s.insert(v); } } void add(int a, int b) { set<Edge*>::iterator itA, itB; Edge* inA = new Edge(b-1); Edge* inB = new Edge(a-1); itA = g[a-1]->e.insert(inA).first; itB = g[b-1]->e.insert(inB).first; inA->set(itB); inB->set(itA); } }; int main() { int n, m, d, a, b; scanf("%d%d%d",&n,&m,&d); Graph g(n); for (int i=0;i<m;++i) { scanf("%d%d",&a,&b); g.add(a, b); } bool again; do { again = false; set<Vertex*>::iterator it = g.s.begin(); while(it != g.s.end()) { Vertex* v = *it; if ((int)v->e.size()<d) { again = true; v->erased = true; g.s.erase(it++); for (set<Edge*>::iterator eit=v->e.begin(); eit!=v->e.end(); ++eit) { Edge *e = *eit; g.g[e->to]->e.erase(e->rev); } v->e.clear(); } else { ++it; } } } while(again); // --- spojne int color = 0; int size = 0; int max_color = 0; int max_size = 0; stack<int> stos; for (set<Vertex*>::iterator it = g.s.begin(); it!=g.s.end(); ++it) { if ((*it)->erased==false && (*it)->c==0) { ++color; size = 0; stos.push((*it)->n); while (!stos.empty()) { int v = stos.top(); stos.pop(); Vertex* ve = g.g[v]; if (ve->erased==false && ve->c==0) { ++size; ve->c = color; for (set<Edge*>::iterator eit=ve->e.begin(); eit!=ve->e.end(); ++eit) { Vertex *vt = g.g[(*eit)->to]; if (vt->erased==false && vt->c==0) { stos.push(vt->n); } } } } if (size>max_size) { max_size = size; max_color = color; } } } // --- wynik if (max_size<2) { printf("NIE\n"); } else { printf("%d\n", max_size); for (set<Vertex*>::iterator it = g.s.begin(); it!=g.s.end(); ++it) { if (max_color == (*it)->c) { printf("%d ", 1+(*it)->n); } } printf("\n"); } return 0; } |