/* * File: main.cpp * Author: luk * * Created on 30 wrzesień 2015, 00:35 */ #include <cstdlib> #include <iostream> using namespace std; /* * */ int a[200001], b[200001]; int usuniete[200001]; int ile_drog[200001],kum[200002],drogi[400001]; int slabe[200001]; int grupa[200001]; int kolejka[200001]; int liczebnosc[200001]; int main() { int n,m,d; cin >> n >> m >> d; int i,j,miasto,drugie; int slabe_n,slabe_i; for(i=0;i<=m;i++) usuniete[i]=0; for(i=0;i<=n;i++) ile_drog[i]=0; a[0]=b[0]=0; for(i=1;i<=m;i++){ cin >> a[i] >> b[i]; ile_drog[a[i]]++; ile_drog[b[i]]++; } kum[0]=0; for(i=1;i<=n+1;i++){ kum[i]=kum[i-1]+ile_drog[i]; } for(i=1;i<=m;i++){ drogi[kum[a[i]]--]=i; drogi[kum[b[i]]--]=i; } slabe_n=0; for(i=1;i<=n;i++) if(ile_drog[i]<d) slabe[++slabe_n]=i; slabe_i=1; while(slabe_i<=slabe_n){ //for(i=1;i<=slabe_n;i++) cout << slabe [i] << " "; //cout << endl; // usun drogi od slabego miasto=slabe[slabe_i]; //cout << " miasto " << miasto << " : "; for(j=kum[miasto]+1;j<=kum[miasto+1];j++){ if(usuniete[drogi[j]]==0){ usuniete[drogi[j]]=1; if(a[drogi[j]]==miasto) drugie=b[drogi[j]]; else drugie=a[drogi[j]]; //cout << " drugie " << drugie << " "; if(ile_drog[drugie]==d) slabe[++slabe_n]=drugie; ile_drog[drugie]--; } } slabe_i++; } // najwieksza spojna skladowa int ile_grup=0, kolejka_i, kolejka_n; for(i=1;i<=n;i++) grupa[i]=0; for(i=1;i<=n;i++) if((ile_drog[i]>=d)&&(grupa[i]==0)){ ile_grup++; grupa[i]=ile_grup; liczebnosc[ile_grup]=1; kolejka_i=1;kolejka_n=1; kolejka[1]=i; while(kolejka_i<=kolejka_n){ miasto=kolejka[kolejka_i]; for(j=kum[miasto]+1;j<=kum[miasto+1];j++){ if(a[drogi[j]]==miasto) drugie=b[drogi[j]]; else drugie=a[drogi[j]]; if((ile_drog[drugie]>=d)&&(grupa[drugie]==0)){ // nie slabe i nie bylo w kolejce kolejka[++kolejka_n]=drugie; grupa[drugie]=ile_grup; liczebnosc[ile_grup]++; } } kolejka_i++; } } int max_licz=0,nr_gr=0; for(i=1;i<=ile_grup;i++) if(liczebnosc[i]>max_licz){ max_licz=liczebnosc[i]; nr_gr=i; } if(ile_grup>0){ cout << max_licz<< endl; for(i=1;i<=n;i++) if(grupa[i]==nr_gr) cout << i << " "; }else cout << "NIE"; 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 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 | /* * File: main.cpp * Author: luk * * Created on 30 wrzesień 2015, 00:35 */ #include <cstdlib> #include <iostream> using namespace std; /* * */ int a[200001], b[200001]; int usuniete[200001]; int ile_drog[200001],kum[200002],drogi[400001]; int slabe[200001]; int grupa[200001]; int kolejka[200001]; int liczebnosc[200001]; int main() { int n,m,d; cin >> n >> m >> d; int i,j,miasto,drugie; int slabe_n,slabe_i; for(i=0;i<=m;i++) usuniete[i]=0; for(i=0;i<=n;i++) ile_drog[i]=0; a[0]=b[0]=0; for(i=1;i<=m;i++){ cin >> a[i] >> b[i]; ile_drog[a[i]]++; ile_drog[b[i]]++; } kum[0]=0; for(i=1;i<=n+1;i++){ kum[i]=kum[i-1]+ile_drog[i]; } for(i=1;i<=m;i++){ drogi[kum[a[i]]--]=i; drogi[kum[b[i]]--]=i; } slabe_n=0; for(i=1;i<=n;i++) if(ile_drog[i]<d) slabe[++slabe_n]=i; slabe_i=1; while(slabe_i<=slabe_n){ //for(i=1;i<=slabe_n;i++) cout << slabe [i] << " "; //cout << endl; // usun drogi od slabego miasto=slabe[slabe_i]; //cout << " miasto " << miasto << " : "; for(j=kum[miasto]+1;j<=kum[miasto+1];j++){ if(usuniete[drogi[j]]==0){ usuniete[drogi[j]]=1; if(a[drogi[j]]==miasto) drugie=b[drogi[j]]; else drugie=a[drogi[j]]; //cout << " drugie " << drugie << " "; if(ile_drog[drugie]==d) slabe[++slabe_n]=drugie; ile_drog[drugie]--; } } slabe_i++; } // najwieksza spojna skladowa int ile_grup=0, kolejka_i, kolejka_n; for(i=1;i<=n;i++) grupa[i]=0; for(i=1;i<=n;i++) if((ile_drog[i]>=d)&&(grupa[i]==0)){ ile_grup++; grupa[i]=ile_grup; liczebnosc[ile_grup]=1; kolejka_i=1;kolejka_n=1; kolejka[1]=i; while(kolejka_i<=kolejka_n){ miasto=kolejka[kolejka_i]; for(j=kum[miasto]+1;j<=kum[miasto+1];j++){ if(a[drogi[j]]==miasto) drugie=b[drogi[j]]; else drugie=a[drogi[j]]; if((ile_drog[drugie]>=d)&&(grupa[drugie]==0)){ // nie slabe i nie bylo w kolejce kolejka[++kolejka_n]=drugie; grupa[drugie]=ile_grup; liczebnosc[ile_grup]++; } } kolejka_i++; } } int max_licz=0,nr_gr=0; for(i=1;i<=ile_grup;i++) if(liczebnosc[i]>max_licz){ max_licz=liczebnosc[i]; nr_gr=i; } if(ile_grup>0){ cout << max_licz<< endl; for(i=1;i<=n;i++) if(grupa[i]==nr_gr) cout << i << " "; }else cout << "NIE"; return 0; } |