Niestety, nie byliśmy w stanie w pełni poprawnie wyświetlić tego pliku, ponieważ nie jest zakodowany w UTF-8. Możesz pobrać ten plik i spróbować otworzyć go samodzielnie. 
  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
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
#include <cstdio>
#include <algorithm>
#include <vector>
#include <stack>
#include <set>

#include "message.h"
#include "sabotaz.h"

using namespace std;

//#define DBG
//#define DBG_D
//#define SINGLE

char msg[1000];

#ifdef SINGLE
int NumberOfNodes() {return 1;}
int MyNodeId() {return 0;}
void PutInt(int target, int value) {}
void Send(int target) {}
int Receive(int source) {return 0;}
int GetInt(int source) {return 0;}

void write(char *msg) {printf(msg);}
#else
#if defined DBG || defined DBG_D
FILE *dbgf;
void write(char *msg) {
  fprintf(dbgf, msg);
  fflush(dbgf);
}
#endif
#endif // SINGLE


int n, m, nodes, node;
int master; // numer w�z�a nadrz�dnego
vector<int> slaves; // numery w�z��w podrz�dnych
int m0, m1; // zakresy most�w dla instancji

///////////////////////////////////////////////////////////////////////////////

struct Wyspa {
  vector<int> mosty;
  bool odw;   // czy odwiedzony
  int nrg;    // numer dzielnicy g��wnej (sp�jnej sk�adowej)
  int poz;    // liczba poziom�w podpi�tych wysp do Union-Find
  int pop;    // poprzednik w drzewie rozpinaj�cym
  int ord;    // porz�dek odwiedzania w drzewie rozpinaj�cym
  int nd;     // liczba potomk�w w drzewie rozpinaj�cym (��cznie z dan� wysp�)
};

Wyspa *MB; // MegaBajtopolis
int *low;  // najmniejszy i najwi�kszy numer w porz�dku drzewa rozpinaj�cego osi�galny z potomka
int *high; // kraw�dzi� niedrzewow�

int *gm;        // g��wne mosty u�yte do wyznaczenia drzewa rozpinaj�cego (kraw�dzie drzewowe)
int *gmA, *gmB; // numery ��czonych wysp
int igm;        // ile jest danych w gm

#ifdef DBG
void dump()
{
  int i;
  for (i = 0; i < n; ++i) {
    sprintf(msg, "i=%d, nrg=%d, pop=%d, ord=%d, nd=%d, low=%d, high=%d\n", i, MB[i].nrg, MB[i].pop, MB[i].ord, MB[i].nd, low[i], high[i]); write(msg);
  }
}
#endif // DBG

////////////////////////////////////////////////////////////////////////////////////////////////////////////
// wys�anie tablicy dane do instancji pid (je�li trzeba to w cz�ciach po 60000 = 240k)
static const int chunk = 1995;
void nadaj(int pid, int *dane, int n)
{
  #ifdef DBG_D
  sprintf(msg, "### %d nadaje do %d (%d)\n", node, pid, n); write(msg);
  #endif // DBG
  PutInt(pid, n); // w pierwszym komunikacie dodatkowo d�ugo�� ca�ej paczki
  if (n == 0) {
    Send(pid);  // tylko info, �e nic nie mamy do przes�ania
    return;
  }
  int nchunks = (n - 1) / chunk + 1;
  for (int k = 0; k < nchunks; ++k) { // ile komunikat�w
    for(int i = k * chunk; i < (k + 1) * chunk && i < n; ++i) PutInt(pid, dane[i]);
    Send(pid);
  }
}

int odbierz(int pid, int *dane)
{
  Receive(pid);
  #ifdef DBG_D
  sprintf(msg, "### %d odbiera od %d (%d)\n", node, pid, n); write(msg);
  #endif // DBG
  int n = GetInt(pid);
  if (n > 0) {
    int nchunks = (n - 1) / chunk + 1;
    for (int k = 0; k < nchunks; ++k) { // ile komunikat�w
      if (k > 0) Receive(pid); // dla pierwszego nie trzeba bo by�o na pocz�tku
      for(int i = k * chunk; i < (k + 1) * chunk && i < n; ++i) dane[i] = GetInt(pid);
    }
  }
  return n;
}

////////////////////////////////////////////////////////////////////////////////////////////////////////////

int *buf;
int findW(int i)
{
  int ib = 0;
  while (MB[i].nrg != i) {
    buf[ib++] = i;
    i = MB[i].nrg;
  }
  for (int j = 0; j < ib; ++j) MB[buf[j]].nrg = i;
  return i;
}

bool unionW(int i, int j)  // przy okazji zwraca czy by�a potrzeba ��czenia
{
  i = findW(i);
  j = findW(j);
  if (i == j)
    return false;
  else if (MB[i].poz > MB[j].poz)
    MB[j].nrg = i;
  else if (MB[i].poz < MB[j].poz)
    MB[i].nrg = j;
  else {
    MB[j].nrg = i;
    MB[i].poz++;
  }
  return true;
}

////////////////////////////////////////////////////////////////////////////////////////////////////////////
// tworzenie drzew rozpinaj�cych

//#define CZYTAJ_WSZ

#ifdef CZYTAJ_WSZ
set<pair<int, int> > wsz;
set<pair<int, int> > drz;
#endif // CZYTAJ_WSZ

void drzewo_rozp()
{
  int i;

  // zapisanie kraw�dzi
#ifdef CZYTAJ_WSZ
  for (i = 0; i < m; ++i) {
    int a = BridgeEndA(i);
    int b = BridgeEndB(i);
    if (a == b) continue;
    if (wsz.find(pair<int, int>(min(a, b), max(a, b))) != wsz.end()) continue;
    wsz.insert(pair<int, int>(min(a, b), max(a, b)));
#else
  for (i = 0; i < igm; ++i) {
    int a = gmA[i];
    int b = gmB[i];
#endif // CZYTAJ_WSZ
    MB[a].mosty.push_back(b);
    MB[b].mosty.push_back(a);
    #ifdef DBG
    sprintf(msg, "%d -- %d\n", a, b); write(msg);
    #endif // DBG
  }
  int ile_grup = 0;
  for (i = 0; i < n; ++i) if (!MB[i].odw) {
    #ifdef DBG
    sprintf(msg, "======\n"); write(msg);
    #endif // DBG
    ile_grup++;
    int ord = 0; // porz�dek odwiedzania
    stack<int> stos;
    stos.push(i);
    MB[i].odw = true;
    MB[i].pop = -1;       // wierzcho�ek drzewa
    while (stos.size()) {
      int k = stos.top();  // wyspa
      MB[k].ord = ord++;
      stos.pop();
      vector<int> &mosty = MB[k].mosty;
      #ifdef DBG
      //sprintf(msg, "k=%d, stos.size=%d mosty=%d\n", k, stos.size(), mosty.size()); write(msg);
      #endif // DBG
      for(int j = 0; j < mosty.size(); ++j) {
        int cel = mosty[j];
        if (!MB[cel].odw) {
          #ifdef DBG
          //sprintf(msg, "  -->%d\n", cel); write(msg);
          #endif // DBG
          MB[cel].odw = true;
          MB[cel].pop = k;
          stos.push(cel);
#ifdef CZYTAJ_WSZ
          drz.insert(pair<int, int>(min(k, cel), max(k, cel)));
#endif // CZYTAJ_WSZ
        }
      }
    }
  }
  #ifdef DBG_D
  sprintf(msg, "drzewo gotowe, grup=%d\n", ile_grup); write(msg);
  #ifdef CZYTAJ_WSZ
  sprintf(msg, "  drz.size=%d\n", drz.size()); write(msg);
  #endif
  #endif // DBG
}

////////////////////////////////////////////////////////////////////////////////////////////////////////////
void obliczaj ()
{
  int i;
  set<int> drzewowe; // kraw�dzie drzewowe
#ifdef CZYTAJ_WSZ
  for (i = 0; i < m; ++i) {
    int a = BridgeEndA(i);
    int b = BridgeEndB(i);
    if (drz.find(pair<int, int>(min(a, b), max(a, b))) != drz.end()) drzewowe.insert(i);
  }
#else
  for (i = 0; i < igm; ++i) drzewowe.insert(gm[i]); // przerzu� drzewowe do seta
#endif // CZYTAJ_WSZ

  for (i = m0; i <= m1; ++i) {
    #ifdef DBG
    sprintf(msg, "i=%d\n", i); write(msg);
    #endif // DBG
    if (drzewowe.find(i) != drzewowe.end()) continue; // na tym etapie nie analizuj drzewowych
    int a = BridgeEndA(i);
    int b = BridgeEndB(i);
    if (a == b) continue; // ignoruj lokalne
    // aktualizuj high/low
    if (MB[a].ord > high[b]) high[b] = MB[a].ord;
    if (MB[b].ord > high[a]) high[a] = MB[b].ord;
    if (MB[a].ord < low[b])  low[b]  = MB[a].ord;
    if (MB[b].ord < low[a])  low[a]  = MB[b].ord;
  }
}

////////////////////////////////////////////////////////////////////////////////////////////////////////////

int obliczaj_serwer()
{
  // oblicz nd, high, low: trzeba przechodzi� po w�z�ach "od do�u" i poprawia� dane w poprzedniku
  int i, v;
  vector<pair<int, int> > kolejnosc;
  for (i = 0; i < n; ++i) {
    #ifdef DBG
    sprintf(msg, "i=%d\n", i); write(msg);
    #endif // DBG
    if (MB[i].ord > 0) {  // wierzcho�ek si� zaktualizuje "od do�u"
      kolejnosc.push_back(pair<int, int>(MB[i].ord, i));   // (porz�dek, numer wyspy)
    }
  }
  sort(kolejnosc.begin(), kolejnosc.end());
  for (i = kolejnosc.size() - 1; i >= 0; --i) {  // teraz od ty�u
    #ifdef DBG
    sprintf(msg, "i=%d\n", i); write(msg);
    #endif // DBG
    v = kolejnosc[i].second;
    int pv = MB[v].pop; // poprzednik
    if (high[v] > high[pv]) high[pv] = high[v];
    if (low[v]  < low[pv])  low[pv]  = low[v];
    MB[pv].nd += MB[v].nd;
  }

  // teraz przejd� drzewowe i szukaj tych, kt�re nie s� w cyklach (bierz kraw�d� do poprzednika)
  int wynik = 0;
  int ile_drz = 0;
  for (v = 0; v < n; ++v) if (MB[v].ord > 0) {
    #ifdef DBG
    sprintf(msg, "v=%d\n", v); write(msg);
    #endif // DBG
    ile_drz++;
    int pv = MB[v].pop;
    if (low[v]  < MB[v].ord ||          // od v lub podrz�dnego mo�na wyj�� niedrzewowo nad pv (lub do niego "dublem")
        high[v] >= MB[v].ord + MB[v].nd)  // od v lub podrz�dnego mo�na wyj�� niedrzewowo gdzie� poza v i jego potomk�w
    {
      // cykl
    }
    else {
      #ifdef DBG
      sprintf(msg, "%d -- %d, low=%d, pv=%d, high=%d, v=%d, nd=%d\n", v, pv, low[v], MB[pv].ord, high[v], MB[v].ord, MB[v].nd); write(msg);
      #endif // DBG
      wynik++;  // kraw�d� drzewowa, kt�ra nie jest w cyklu
    }
  }
  #ifdef DBG_D
  sprintf(msg, "serwer obliczyl, ile_drz=%d\n", ile_drz); write(msg);
  #endif // DBG

  return wynik;
}

////////////////////////////////////////////////////////////////////////////////////////////////////////////

int main()
{
  int i, j;
  #ifdef SINGLE
  LibInit();
  #endif // SINGLE

  n = NumberOfIsles();
  m = NumberOfBridges();
  node = MyNodeId();

  nodes = min(NumberOfNodes(), 1 + m / 100000); // ograniczenie liczby instancji aby ka�da mia�a min. 50-100k (lub ca�o�� dla n < 100k)
  if (node >= nodes) return 0; // niepotrzebna instancja

  #ifndef SINGLE
  #if defined DBG || defined DBG_D
  char fname[200];
  sprintf(fname, "node%02d.log", node);
  dbgf = fopen(fname, "w");
  #endif // defined
  #endif // SINGLE

  master = (node + 1) / 2 - 1;
  j = (node + 1) * 2 - 1; // pierwszy numer w�z�a podrz�dnego
  for (i = 0; i <= 1 && i + j < nodes; ++i)
    slaves.push_back(j + i);

  int s = m / nodes;     // d�ugo�� jednej sekcji
  m0 = node * s; // pozycja pocz�tkowa
  m1 = (node == nodes - 1 ? m - 1 : (node + 1) * s - 1); // pozycja ko�cowa

  #ifdef DBG
  sprintf(msg, "node=%d, n=%d, m=%d (%d..%d), slaves=%d\n", node, n, m, m0, m1, slaves.size());
  write(msg);
  #endif // DBG

  MB = new Wyspa[n];
  gm = new int[n];
  gmA = new int[n];
  gmB = new int[n];
  buf = new int[n];
  low = new int[n];
  high = new int[n];

  for (i = 0; i < n; ++i) {
    MB[i].odw = false;
    MB[i].nrg = i; // na pocz�tek ka�da wyspa jest samotna
    MB[i].poz = 0;
    low[i] = n + 1;  // na razie nie ma osi�galnych niedrzewowymi, +1 na zapas :-)
    high[i] = -1;
    MB[i].nd = 1;   // sam jak palec
  }

  // wczytanie danych
  igm = 0;
  for (i = m0; i <= m1; ++i) {
    int a = BridgeEndA(i);
    int b = BridgeEndB(i);
    #ifdef DBG
    //sprintf(msg, "i=%d, a=%d, b=%d\n", i, a, b); write(msg);
    #endif // DBG
    if (a != b)  // ignoruj lokalne
      if (unionW(a, b)) {
        gm[igm] = i;  // numer kraw�dzi rozpinaj�cej
        gmA[igm] = a;
        gmB[igm] = b;
        igm++;
      }
  }

  #ifdef DBG_D
  set<int> grupy;
  for (i = 0; i < n; ++i)
    grupy.insert(findW(i));
  sprintf(msg, "wczytane n=%d, grup=%d igm=%d\n", n, grupy.size(), igm);
  write(msg);
  #endif // DBG

  // -----------------------------------------------------------------------------------------------
  // scal dane od podrz�dnych instancji
  int *sgm = new int[n];
  int isgm;
  for (int sl = 0; sl < slaves.size(); ++sl) {
    isgm = odbierz(slaves[sl], sgm);
    #ifdef DBG_D
    sprintf(msg, "odebrane od %d\n", slaves[sl]); write(msg);
    #endif // DBG
    for (i = 0; i < isgm; ++i) {
      int a = BridgeEndA(sgm[i]);
      int b = BridgeEndB(sgm[i]);
      if (a != b)  // ignoruj lokalne
        if (unionW(a, b)) {
          gm[igm] = sgm[i];  // numer kraw�dzi u�ytej do po��czenia dzielnic
          gmA[igm] = a;
          gmB[igm] = b;
          igm++;
        }
    }
  }
  if (node > 0) { // wys�anie do mastera i odebranie finalnej listy kraw�dzi rozpinaj�cych
    nadaj(master, gm, igm);
    #ifdef DBG_D
    sprintf(msg, "gm wyslane do mastera %d\n", master); write(msg);
    #endif // DBG
    igm = odbierz(master, gm);
    #ifdef DBG_D
    sprintf(msg, "gm odebrane od mastera %d\n", master); write(msg);
    #endif // DBG
  }
  for (int sl = 0; sl < slaves.size(); ++sl) {  // rozes�anie do podrz�dnych
    nadaj(slaves[sl], gm, igm);
    #ifdef DBG_D
    sprintf(msg, "gm nadane do %d\n", slaves[sl]); write(msg);
    #endif // DBG
  }

  // -----------------------------------------------------------------------------------------------
  #ifdef DBG
  sprintf(msg, "start obliczen\n");
  write(msg);
  #endif // DBG
  drzewo_rozp();
  obliczaj();
  #ifdef DBG
  sprintf(msg, "obliczone\n"); write(msg);
  #endif // DBG
  // -----------------------------------------------------------------------------------------------
  // scal high/low podrz�dnych instancji
  int *shi = new int[n];
  int *slo = new int[n];

  for (int sl = 0; sl < slaves.size(); ++sl) {
    odbierz(slaves[sl], shi); // wiadomo, �e odbieram n
    odbierz(slaves[sl], slo);
    #ifdef DBG_D
    sprintf(msg, "lo/hi odebrane od %d\n", slaves[sl]); write(msg);
    #endif // DBG
    for (i = 0; i < n; ++i) {
      if (shi[i] > high[i]) high[i] = shi[i];
      if (slo[i] < low[i])  low[i]  = slo[i];
    }
  }
  if (node > 0) { // wys�anie do mastera
    nadaj(master, high, n);
    nadaj(master, low, n);
    #ifdef DBG_D
    sprintf(msg, "lo/hi nadane do mastera\n"); write(msg);
    #endif // DBG
  }

  // -----------------------------------------------------------------------------------------------
  if (node == 0) {
    int wynik = obliczaj_serwer();
    printf("%d\n", wynik);
    #ifdef DBG
    dump();
    sprintf(msg, "wynik=%d\n", wynik); write(msg);
    #endif // DBG
  }
  #ifdef DBG
  else
    dump();
  #endif // DBG
}