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

//#define DEBUG

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

#ifndef DEBUG
#define NDEBUG
#endif
#include<assert.h>

using namespace std;

class Node;

int nodes;      //!< Liczba wierzchołków
int edges;      //!< Liczba krawędzi
Node* node;     //!< Wierzchołki
vector<int> treeEdges;      //!< Wierzchołki drzewa spinającego - potęcjalni kandydaci

class Node {
private:
    Node* target;
public:
    void init() {
        target=this;
    }

    void clear() {
        target=this;
    }

    inline Node* getTarget() {
        if(target==this) return this;
        return target=target->getTarget();
    }

    inline void connect(Node* t) {
        this->target=t;
    }
};

// Kruskala algorytm drzewa spinającego

/**
 * Funkcja sprawdzająca, czy zadana krawędź zmienia liczbę drzew spinających
 */
bool checkEdge(int e) {
    // resetujemy dane
    for(int i=0;i<nodes;++i) node[i].clear();
    // budujemy normalnie drzewo bez podejrzanej krawędzi
    for(int i=0;i<edges;++i) {
        if(i==e) continue;  // pomijamy wadliwą krawędz
        Node* na=&node[BridgeEndA(i)];
        Node* nb=&node[BridgeEndB(i)];
        Node* ta=na->getTarget();
        Node* tb=nb->getTarget();
        if(ta==tb) continue;    // ta krawedź nie zmniejszy liczby drzew, więc ją ignorujemy
        ta->connect(tb);          // podpinamy jeden do drugiego
    }
    // na koniec sprawdzamy, czy boki podejrzanej krawędzi są w różnych drzewach, jak tak to dzielący most
    {
        Node* na=&node[BridgeEndA(e)];
        Node* nb=&node[BridgeEndB(e)];
        Node* ta=na->getTarget();
        Node* tb=nb->getTarget();
        return ta!=tb;  // jeżeli dwa różne drzewa
    }
}

int main(int argc, char** argv) {
    log("Starting with %d islands and %d bridges",(int)NumberOfIsles(), (int)NumberOfBridges());
    nodes=NumberOfIsles();
    edges=NumberOfBridges();
    node=(Node*)malloc(sizeof(Node)*nodes);

    //if(MyNodeId()!=0) return 0;

    // etap 0 - przygotowanie danych
    // inicjalizacja wierzchołków - i każdy z nich jest drzewem
    for(int i=0;i<nodes;++i) node[i].init();
    // połączenie wszystkich wierzchołków w jeden, aby znaleźć różne grupy (wiele różnych wierzchołków)
    for(int i=0;i<edges;++i) {
        Node* na=&node[BridgeEndA(i)];
        Node* nb=&node[BridgeEndB(i)];
        Node* ta=na->getTarget();
        Node* tb=nb->getTarget();
        if(ta==tb) continue;    // ta krawedź nie zmniejszy liczby drzew, więc ją ignorujemy
        ta->connect(tb);          // podpinamy jeden do drugiego
        treeEdges.push_back(i); // kandydat
    }
    log("Got %d tree edges",treeEdges.size());

    int jobs=(treeEdges.size()+NumberOfNodes()-1)/NumberOfNodes();  // tyle przypada na jednen komputer
    int from=jobs*MyNodeId();
    int to=from+jobs;
    if(to>treeEdges.size()) to=treeEdges.size();

    log("Processing from %d to %d (total: %d)",from,to,treeEdges.size());

    int res=0;
    for(int i=from;i<to;++i) {
        if((i-from)%100==0) log("Checking %d",i);
        if(checkEdge(treeEdges[i])) ++res;
    }

    if(MyNodeId()!=0) {
        PutInt(0,res);
        Send(0);
        return 0;
    }
    for(int i=1;i<NumberOfNodes();++i) {
        Receive(i);
        int v=GetInt(i);
        log("Received %d from node %d",v);
        res+=v;
    }

    printf("%d\n",res);

    return 0;
}