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
#include <cstdio>
#include <map>
#include <set>
#include <list>

typedef std::set<int>   VSet;

struct  Vertex  {
    int     id;
    bool    seen;
    VSet    edges;
    Vertex() : id(0), seen(false) {}
    Vertex(int _id) : id(_id), seen(false) {}
};

typedef std::map<int, Vertex*>  Map;
typedef std::list<Vertex*>      Queue;

int main(void)
{
    int n, m, d;
    Map map, *bcc;

    scanf("%d%d%d", &n, &m, &d);

    for (int i = 0; i < m; i++) {
        int     a, b;
        Vertex  *va, *vb;

        scanf("%d%d", &a, &b);

        if (!(va = map[a]))
            map[a]  = va    = new Vertex(a);

        if (!(vb = map[b]))
            map[b]  = vb    = new Vertex(b);

        va->edges.insert(b);
        vb->edges.insert(a);
    }

    bcc = NULL;

    while (!map.empty()) {
        Map             *cc = new Map;
        Queue           q;
        Map::iterator   i;

        i   = map.begin();
        q.push_back(i->second);

        while (!q.empty()) {
            Vertex  *v, *v2;

            v               = q.front();
            v->seen         = true;
            (*cc)[v->id]    = v;
            q.pop_front();

            for(VSet::iterator e = v->edges.begin(); e != v->edges.end(); ++e)
                if ((i = map.find(*e)) != map.end() && (v2 = i->second) && !v2->seen)
                    q.push_back(v2);
        }

        for (i = cc->begin(); i != cc->end(); ++i) {
            map.erase(i->first);

            if (i->second->edges.size() < d)
                q.push_back(i->second);

            else
                i->second->seen = false;
        }

        while (!q.empty()) {
            Vertex  *v, *v2;

            v   = q.front();
            q.pop_front();

            for(VSet::iterator e = v->edges.begin(); e != v->edges.end(); ++e) {
                v2  = (*cc)[*e];
                v2->edges.erase(v->id);

                if (!v2->seen && v2->edges.size() < d) {
                    v2->seen    = true;
                    q.push_back(v2);
                }
            }

            cc->erase(v->id);
            delete  v;
        }

        if (!bcc || cc->size() > bcc->size())
            bcc = cc;
    }

    if (!bcc || !bcc->size())
        printf("NIE\n");

    else {
        printf("%lu\n", bcc->size());

        for (Map::iterator i = bcc->begin(); i != bcc->end(); ++i)
            printf("%d ", i->first);

        printf("\n");
    }

    return  0;
}