#include <cstdio> #include <algorithm> #include <queue> #include <vector> #define MAXN 200001 using namespace std; typedef pair<int,int> PII; bool wierzcholekUsuniety[MAXN], vis[MAXN]; int n,m,d; int stopienWierzcholka[MAXN]; vector<int> v[MAXN], spojnaSkladowa[MAXN]; priority_queue<PII> q; void dfs (int x, int y){ vis[x] = true; spojnaSkladowa[y].push_back(x); //dorzucamy wierzcholek do aktualnej spojnej skladowej for (int i=0; i<v[x].size(); ++i){ if (!vis[v[x][i]] && !wierzcholekUsuniety[v[x][i]]){ dfs(v[x][i], y); } } return; } int main(){ scanf("%d%d%d", &n, &m, &d); for (int i=0; i<m; ++i){ int x,y; scanf("%d%d", &x, &y); v[x].push_back(y); v[y].push_back(x); } for(int i=1; i<=n; ++i){ stopienWierzcholka[i] = v[i].size(); wierzcholekUsuniety[i] = false; q.push(PII(-stopienWierzcholka[i], i)); } //ODCHUDDZENIE GRAFU while (!q.empty()){ PII gora = q.top(); q.pop(); int stopien = -gora.first; int wierzcholekA = gora.second; if (stopien < d && !wierzcholekUsuniety[wierzcholekA]){ //trzeba usunac ten wierzcholek z grafu (i juz nigdy do niego nie wchodzic) wierzcholekUsuniety[wierzcholekA] = true; for (int i=0; i<v[wierzcholekA].size(); ++i){ int wierzcholekB = v[wierzcholekA][i]; if (!wierzcholekUsuniety[wierzcholekB]){ //wszak nie moge wejsc do wierzcholka, ktory zostal juz usuniety!! --stopienWierzcholka[wierzcholekB]; q.push(PII(-stopienWierzcholka[wierzcholekB], wierzcholekB)); } } } //nie ma sensu juz przegladac wierzcholkow, wszystkie beda mialy stopien wiekszy niz 'd' } //ZNALEZNIENIE WSPOLNYCH SKLADOWYCH int nrSkladowej = 0; for (int i=1; i<=n; ++i){ if (!vis[i] && !wierzcholekUsuniety[i]){ ++nrSkladowej; dfs(i, nrSkladowej); } } //ZNALEZNIENIE NAJWIEKSZEJ WSPOLNEJ SKLADOWEJ int nrNajwiekszejSkladowej = 1; for (int i=1; i<=nrSkladowej; ++i){ if (spojnaSkladowa[nrNajwiekszejSkladowej].size() < spojnaSkladowa[i].size()){ nrNajwiekszejSkladowej = i; } } if (spojnaSkladowa[nrNajwiekszejSkladowej].size()){ printf("%d\n", spojnaSkladowa[nrNajwiekszejSkladowej].size()); sort(spojnaSkladowa[nrNajwiekszejSkladowej].begin(), spojnaSkladowa[nrNajwiekszejSkladowej].end()); for (int i=0; i<spojnaSkladowa[nrNajwiekszejSkladowej].size(); ++i){ printf("%d ", spojnaSkladowa[nrNajwiekszejSkladowej][i]); } } else{ printf("NIE"); } printf("\n"); return 0; }
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 | #include <cstdio> #include <algorithm> #include <queue> #include <vector> #define MAXN 200001 using namespace std; typedef pair<int,int> PII; bool wierzcholekUsuniety[MAXN], vis[MAXN]; int n,m,d; int stopienWierzcholka[MAXN]; vector<int> v[MAXN], spojnaSkladowa[MAXN]; priority_queue<PII> q; void dfs (int x, int y){ vis[x] = true; spojnaSkladowa[y].push_back(x); //dorzucamy wierzcholek do aktualnej spojnej skladowej for (int i=0; i<v[x].size(); ++i){ if (!vis[v[x][i]] && !wierzcholekUsuniety[v[x][i]]){ dfs(v[x][i], y); } } return; } int main(){ scanf("%d%d%d", &n, &m, &d); for (int i=0; i<m; ++i){ int x,y; scanf("%d%d", &x, &y); v[x].push_back(y); v[y].push_back(x); } for(int i=1; i<=n; ++i){ stopienWierzcholka[i] = v[i].size(); wierzcholekUsuniety[i] = false; q.push(PII(-stopienWierzcholka[i], i)); } //ODCHUDDZENIE GRAFU while (!q.empty()){ PII gora = q.top(); q.pop(); int stopien = -gora.first; int wierzcholekA = gora.second; if (stopien < d && !wierzcholekUsuniety[wierzcholekA]){ //trzeba usunac ten wierzcholek z grafu (i juz nigdy do niego nie wchodzic) wierzcholekUsuniety[wierzcholekA] = true; for (int i=0; i<v[wierzcholekA].size(); ++i){ int wierzcholekB = v[wierzcholekA][i]; if (!wierzcholekUsuniety[wierzcholekB]){ //wszak nie moge wejsc do wierzcholka, ktory zostal juz usuniety!! --stopienWierzcholka[wierzcholekB]; q.push(PII(-stopienWierzcholka[wierzcholekB], wierzcholekB)); } } } //nie ma sensu juz przegladac wierzcholkow, wszystkie beda mialy stopien wiekszy niz 'd' } //ZNALEZNIENIE WSPOLNYCH SKLADOWYCH int nrSkladowej = 0; for (int i=1; i<=n; ++i){ if (!vis[i] && !wierzcholekUsuniety[i]){ ++nrSkladowej; dfs(i, nrSkladowej); } } //ZNALEZNIENIE NAJWIEKSZEJ WSPOLNEJ SKLADOWEJ int nrNajwiekszejSkladowej = 1; for (int i=1; i<=nrSkladowej; ++i){ if (spojnaSkladowa[nrNajwiekszejSkladowej].size() < spojnaSkladowa[i].size()){ nrNajwiekszejSkladowej = i; } } if (spojnaSkladowa[nrNajwiekszejSkladowej].size()){ printf("%d\n", spojnaSkladowa[nrNajwiekszejSkladowej].size()); sort(spojnaSkladowa[nrNajwiekszejSkladowej].begin(), spojnaSkladowa[nrNajwiekszejSkladowej].end()); for (int i=0; i<spojnaSkladowa[nrNajwiekszejSkladowej].size(); ++i){ printf("%d ", spojnaSkladowa[nrNajwiekszejSkladowej][i]); } } else{ printf("NIE"); } printf("\n"); return 0; } |