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
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

    void DFS( vector<vector<int> > &H, vector<int> &nr, vector<int> &skladowe, int nr_liczba, int v){
        nr[v] = nr_liczba;
        skladowe[nr_liczba]++;
        for(int i = 0; i < H[v].size(); ++i)
            if(nr[H[v][i]] == 0)
                DFS(H, nr, skladowe, nr_liczba, H[v][i]);
    }

int main(){
    ios_base::sync_with_stdio(0);
    int n, m, d, a, b, G_size;
    cin >> n >> m>> d;
    G_size = n;
    vector<bool> part(n+1, true);
    vector<bool> do_usun(n+1, false);
    vector<vector<int> > G(n+1, vector<int>(0));
    vector<int> st(n+1, 0);
    for(int i = 0; i < m; ++i){
        cin >>a >> b;
        G[a].push_back(b);
        G[b].push_back(a);
        st[a]++;
        st[b]++;
    }
    queue<int> kol;
    for(int i = 1; i <=n; ++i){
        if(st[i] < d){
            kol.push(i);
            do_usun[i] = true;
        }
    }
    while(!kol.empty()){
        // USUN KOLEJNY WIERZCHOLEK
        a = kol.front();
        kol.pop();
        //cout <<"Wywalam "<< a<< endl;
        for(int i = 0; i < G[a].size(); ++i){
            if(part[G[a][i]]){
                st[G[a][i]]--;
                if(st[G[a][i]] < d and !do_usun[G[a][i]]){
                    //cout << st[G[a][i]] <<" "<< do_usun[G[a][i]] <<endl;
                    do_usun[G[a][i]] = true;
                    //cout<< "Dodaje do usun "<< G[a][i]<<endl;
                    kol.push(G[a][i]);
            }
        }
        }
        G_size--;
        part[a] = false;
    }
    // II PART ROZWIAZANIA
    if( G_size == 0)
        cout << "NIE";
    else{
        vector<vector<int> > H(n+1, vector<int>(0));
        for(int i = 1; i <=n; ++i){
            if(part[i]){
                for(int j = 0; j < G[i].size(); ++j){
                    if(part[G[i][j]]){
                        H[i].push_back(G[i][j]);
                        H[G[i][j]].push_back(i);
                    }
                }
            }
        }
        int nr_liczba = 0;
        vector<int> skladowe(1,0);
        vector<int> nr(n+1,0);
        for(int i = 1; i<=n; ++i){
            if(part[i] and nr[i] == 0 ){
                skladowe.push_back(0);
                nr_liczba++;
                DFS(H, nr, skladowe, nr_liczba, i);
            }
        }
    int max_nr = 0;
    for(int i = 1; i<= nr_liczba; ++i)
        if(skladowe[i] > skladowe[max_nr])
            max_nr = i;
    cout << skladowe[max_nr] << endl;
    for(int i = 1; i <= n; ++i){
        if (nr[i] == max_nr)
            cout << i << " "; // 1111 OSTATNIA SPACJA SPR. 1111
    }
    }
}