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
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int n, m, d;
    cin >> n >> m >> d;
    vector <int> MiastoP;
    vector <int> MiastoD;
    int IloscPolaczen[n];
    for(int i=0; i < n; i++)
    {
        IloscPolaczen[i] = 0;
    }
    int poczatek, koniec;
    //Wczytanie danych
    for(int i=0; i < m; i++)
    {
        cin >> poczatek >> koniec;
        MiastoP.push_back(poczatek);
        MiastoD.push_back(koniec);
        IloscPolaczen[poczatek - 1]++;
        IloscPolaczen[koniec - 1]++;
    }
    //Usuniecie miast nie spelniajacych warunkow
    bool ZnalezioneDoSpr;
    int IloscDrog;
    do
    {
        ZnalezioneDoSpr = false;
        IloscDrog = MiastoP.size();
        for(int i=0; i < IloscDrog; i++)
        {
            if(!MiastoP.size())
            {
                break;
            }
            if(IloscPolaczen[MiastoP[i] - 1] < d && IloscPolaczen[MiastoP[i] - 1])
            {
                ZnalezioneDoSpr = true;
                IloscPolaczen[MiastoP[i] - 1]--;
                IloscPolaczen[MiastoD[i] - 1]--;
                MiastoP.erase(MiastoP.begin() + i);
                MiastoD.erase(MiastoD.begin() + i);
            }
            if(!MiastoP.size())
            {
                break;
            }
            if(i == MiastoP.size())
            {
                i=-1;
                continue;
            }
            if(IloscPolaczen[MiastoD[i] - 1] < d && IloscPolaczen[MiastoD[i] - 1] && !ZnalezioneDoSpr)
            {
                ZnalezioneDoSpr = true;
                IloscPolaczen[MiastoP[i] - 1]--;
                IloscPolaczen[MiastoD[i] - 1]--;
                MiastoP.erase(MiastoP.begin() + i);
                MiastoD.erase(MiastoD.begin() + i);
            }
            if(ZnalezioneDoSpr)
            {
                i--;
                ZnalezioneDoSpr = false;
            }
            if(i == (MiastoP.size() - 1))
            {
                i=0;
                if(!ZnalezioneDoSpr)
                {
                    break;
                }
            }
        }
    }while(ZnalezioneDoSpr);
    if(!MiastoP.size())
    {
        cout << "NIE";
        return 0;
    }
    vector <int> Zbior;
    vector <int> ZbiorNajwiekszy;
    vector <int> DoSprawdzenia;
    int start = MiastoP[0];
    DoSprawdzenia.push_back(start);
    int x = 0;
    int y;
    bool Wyliczone, CzyJuzSprawdzano;
    do
    {
        IloscDrog = MiastoP.size();
        y = 0;
        Wyliczone = false;
        for(int i=0; i < IloscDrog; i++)
        {
            if(MiastoP[i] == start)
            {
                DoSprawdzenia.push_back(MiastoD[y]);
                MiastoP.erase(MiastoP.begin() + y);
                MiastoD.erase(MiastoD.begin() + y);
                y--;
            }
            if(MiastoD[i] == start)
            {
                DoSprawdzenia.push_back(MiastoP[y]);
                MiastoP.erase(MiastoP.begin() + y);
                MiastoD.erase(MiastoD.begin() + y);
                y--;
            }
            y++;
        }
        Zbior.push_back(start);
        x++;
        if(x == DoSprawdzenia.size())
        {
            if(MiastoP.size() > Zbior.size())
            {
                if(Zbior.size() > ZbiorNajwiekszy.size())
                {
                    Zbior.swap(ZbiorNajwiekszy);
                }
                DoSprawdzenia.clear();
                Zbior.clear();
                DoSprawdzenia.push_back(MiastoP[0]);
                x=0;
            }
            else
            {
                if(Zbior.size() > ZbiorNajwiekszy.size())
                {
                    Zbior.swap(ZbiorNajwiekszy);
                }
            }
            Wyliczone = true;
        }
        for(x; x < DoSprawdzenia.size(); x++)
        {
            CzyJuzSprawdzano = false;
            for(int i=0; i < x; i++)
            {
                if(DoSprawdzenia[i] == DoSprawdzenia[x])
                {
                    CzyJuzSprawdzano = true;
                    break;
                }
            }
            if(!CzyJuzSprawdzano)
            {
                start = DoSprawdzenia[x];
                break;
            }
        }
    }while(ZbiorNajwiekszy.size() < MiastoP.size() || !Wyliczone);
    int DoWypisania = ZbiorNajwiekszy.size();
    cout << DoWypisania << endl;
    for(int i=0; i < DoWypisania; i++)
    {
        cout << ZbiorNajwiekszy[i] << " ";
    }
    return 0;
}