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
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>


using namespace std;


vector<set<int> > polaczenia; //kazdemu miastu przyporzadkowuje zbior miast polaczonych z nim droga


void usun_miasto(int miasto, int d, vector<bool>& do_usuniecia)
{
    if (do_usuniecia[miasto]==false &&
            polaczenia[miasto].size() < (unsigned)d)
    {
        do_usuniecia[miasto]=true;
        for (set<int>::iterator it=polaczenia[miasto].begin();
             it!=polaczenia[miasto].end(); ++it)
        {
            polaczenia[*it].erase(miasto);
            usun_miasto(*it, d, do_usuniecia);
        }
        polaczenia[miasto].clear();
    }
}


void znajdz_grupe(int miasto, vector<bool>& sprawdzone_miasta,
                  set<int>& grupa)
{
    if (sprawdzone_miasta[miasto] == false)
        //miasto nie bylo sprawdzone
    {
        sprawdzone_miasta[miasto] = true;
        grupa.insert(miasto);

        for(set<int>::iterator it=polaczenia[miasto].begin();
            it!=polaczenia[miasto].end(); ++it)
        {
            znajdz_grupe(*it, sprawdzone_miasta, grupa);
        }
    }
}


int main()
{
    int ile_miast, ile_drog, d, m1, m2;
    cin>> ile_miast >>ile_drog >>d;

    polaczenia.resize(ile_miast+1, {});
    for (int ii=0; ii<ile_drog; ii++)
    {
        cin >>m1 >>m2;
        polaczenia[m1].insert(m2);
        polaczenia[m2].insert(m1);
    }

    //wstepna eliminacja - usuwanie miast o mniej niz d polaczeniach z innymi:
    vector<bool> do_usuniecia = vector<bool>(polaczenia.size(), false);

    for (unsigned int miasto=1; miasto<polaczenia.size(); miasto++)
        usun_miasto(miasto, d, do_usuniecia);


    //znalezienie najwiekszej grupy polaczonych ze soba miast:
    vector<bool> sprawdzone_miasta = vector<bool>(polaczenia.size(), false);
    set<int> grupa, najw_grupa;

    for (unsigned int miasto=1; miasto<polaczenia.size(); miasto++)
    {
        znajdz_grupe(miasto, sprawdzone_miasta, grupa);
        if (grupa.size() > najw_grupa.size())
            swap(grupa, najw_grupa);
        grupa.clear();
    }


    // wyswietlenie wynikow:
    int ile = najw_grupa.size();
    if (ile==1)
        cout<<"NIE"<<endl;
    else
    {
        cout<<ile<<endl;
        for (auto it = najw_grupa.begin(); it!=najw_grupa.end(); ++it)
            cout <<*it<<" ";
        cout<<endl;
    }

    return 0;
}