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
#include<stdio.h>
#include<stdlib.h>
#include<vector>

#ifndef DEBUG
#define NDEBUG
#endif

#include<assert.h>

#ifdef DEBUG
#define log(format, ...)     printf(format "\n", __VA_ARGS__)
#else
#define log(...)
#endif


using namespace std;

class Edge;
class Node;

Edge* edges;
Node* nodes;

class Node {
public:
    int count;
	int group;
    Edge* edges;    //
public:
    Node() : count(0), group(0), edges(NULL) {}

};


/**
 * Krawedź w postaci
 * celu (to) oraz adresu do następnej krawędzi (lista jednokierunkowa)
 */
class Edge {
public:
    Node* to;
    Edge* next;
public:
    void init(Node* from, Node* target) {
        assert(from!=NULL && target!=NULL);
        assert(from!=target);
        to=target;              // zapisujemy adres do
        next=from->edges;   // łączymy z obecnym początkiem listy
        from->edges=this;   // ustawiamy nowy początek listy na aktualną krawędź
        from->count++;      // aktualizacja licznika
    }
};



int main(int argc, char** argv) {
	int n,m,d;
	// etap 0 - wczytanie danych
	scanf("%d %d %d",&n,&m,&d);

	nodes=new Node[n+1]();  // bo indeks od 1
	edges=(Edge*)malloc(sizeof(Edge)*m*2);      // x2 bo osobno mamy w jedną i drugą stronę, bo używamy jako listy

    //log("Loading %d edges for %d nodes",m,n);
	for(int i=0;i<m;++i) {
		int a,b;
		scanf("%d %d",&a,&b);
		//log("Adding node %d %d",a,b);
		edges[i*2].init(&nodes[a],&nodes[b]);
		edges[i*2+1].init(&nodes[b],&nodes[a]);
	}
	// etap 1 - odrzucanie wierzcholkow nie spelniajacych warunku ilosci drog
    vector<Node*> toProces;
    for(int i=1;i<=n;++i) {
        Node* ni=&nodes[i];
        if(ni->count<d) {
            ni->group=-1;
            toProces.push_back(ni); // dodajemy do listy do przetworzenia
        }
    }
    // obsługujemy listę (jako stos) do przetworzenia
    while(toProces.size()>0) {
        Node* pn=toProces.back();
        toProces.pop_back();
        log("Removing node %d",(pn-nodes));
        for(Edge* e=pn->edges;e!=NULL;e=e->next) {  // przejście po liście wierzchołków
            Node* tn=e->to;
            if(tn->group==-1) continue;   // oznaczone do usunięcia lub już usunięte nie ma co przetwarzać kolejny raz - ignorujemy
            if(--tn->count <d) { // zmniejszamy licznik dróg i jeżeli obniży poniżej wartości wymaganej to oznaczamy jako do usunięcia
                tn->group=-1;
                toProces.push_back(tn);
            }
        }
    }
    // etap 2
    // wierzchołki, które pozostały spełniają wartunek liczebności dróg
    // jedynie należy sprawdzić spójności i wybrać największą
    int bestGroup=0;    //!< Grupa o największej liczebności
    int bestSize=0;
    {
        int groupIndex=0;   //!< Indeks kolejnej grupy
        for(int i=1;i<=n;++i) {
            if(nodes[i].group==0) { // jeżeli wierzchołek nie przydzielony do żadnej grupy, to zaczynamy dla niego wyliczać grupę
                int groupSize=1;
                ++groupIndex;       // zwiększamy licznik grupy
                toProces.push_back(&nodes[i]);      // Używamy tej samej listy jako stosu do przechodzenia po wierzchołkach
                nodes[i].group=groupIndex;
                while(toProces.size()>0) {
                    Node* pn=toProces.back();
                    toProces.pop_back();
                    log("Processing node %d for group %d",pn-nodes, groupIndex);
                    for(Edge* e=pn->edges;e!=NULL;e=e->next) {  // przejście po liście wierzchołków
                        Node* tn=e->to;
                        if(tn->group==-1) continue; // pomijamy usunięte
                        assert(tn->count>=d);       // docelowy wierzchołek musi miec wymaganą ilość dróg
                        if(tn->group==0) {
                            log("  Adding connected node %d", tn-nodes);
                            tn->group=groupIndex;   // zapisujemu indeks grupy
                            ++groupSize;            // zwiększamy licznik rozmiaru
                            toProces.push_back(tn); // dodajemy do przetworzenian a stos
                        } else assert(tn->group==groupIndex);    // jeżeli wierzchołek nie jest wolny, to musi byc w tej samej grupie
                    }
                }
                log("Processing node %d done. %d nodes in %d group",i,groupSize,groupIndex);
                if(groupSize>bestSize) {
                    bestSize=groupSize;
                    bestGroup=groupIndex;
                }
            }
        }
    }

    // etap 3 - wypisanie wyniku dla najliczniejszej grupy
    if(bestSize==0) {
        printf("NIE\n");
    } else {
        printf("%d\n",bestSize);
        for(int i=1;i<=n;++i) {
            if(nodes[i].group==bestGroup) printf("%d ",i); // wypisujemy członków grupy o właściwym indeksie
        }
        printf("\n");
    }
	return 0;
}