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
#include <vector>
#include <cstdio>
#include <queue>
#include <algorithm>

using namespace std;

int main()
{
    int max_group = 0, cities, roads, d;

    scanf("%d %d %d", &cities, &roads, &d);

    vector<vector<int>> graph(cities+1);
    vector<int> connections(cities+1,0);
    vector<int> visited(cities+1,0);

    int c1, c2;

    for(int z=0; z<roads; z++)
    {
        scanf("%d %d", &c1, &c2);
        graph[c1].push_back(c2);
        graph[c2].push_back(c1);
        connections[c1]++;
        connections[c2]++;
    }

    bool changed = true;

    while(changed)
    {
        changed = false;
        for(int z=0; z<cities+1; z++)
        {
            if(connections[z] > 0 && connections[z] < d)
            {
                changed = true;
                connections[z] = 0;
                for(unsigned int x=0; x<graph[z].size(); x++)
                    connections[graph[z][x]]--;
            }
        }
    }

    queue<int> que;
    int act_group, act;
    vector<int> act_members;
    vector<int> max_members;

    for(int z=0; z<cities+1; z++)
    {
        if(connections[z] > 0 && !visited[z])
        {
            act_group = 1;
            que.push(z);
            visited[z] = 1;
            act_members.clear();
            act_members.push_back(z);
            while(!que.empty())
            {
                act = que.front();
                que.pop();
                for(unsigned int x=0; x<graph[act].size(); x++)
                {
                    if(!visited[graph[act][x]] && connections[graph[act][x]] >= d)
                    {
                        visited[graph[act][x]] = 1;
                        act_group++;
                        que.push(graph[act][x]);
                        act_members.push_back(graph[act][x]);
                    }
                }
            }
            if(act_group > max_group)
                max_group = act_group;
                max_members = act_members;
        }
        else
            visited[z] = 1;
    }

    if(max_group == 0)
        printf("NIE");
    else
    {
        printf("%d\n", max_group);
        sort(max_members.begin(), max_members.end());
        for(unsigned int z=0; z<max_members.size(); z++)
            if(z < max_members.size()-1)
                printf("%d ", max_members[z]);
            else
                printf("%d", max_members[z]);
    }

    return 0;
}