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

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200 * 1000;

int N, M, in[MAXN], low[MAXN], dfstime, bridges;
vector<pair<int, int>> graph[MAXN];
vector<pair<int, int>> edges;

void visit(int u, int parent) {
  low[u] = in[u] = dfstime++;
  for (auto edge : graph[u]) {
    int v, edge_id;
    tie(v, edge_id) = edge;
    if (edge_id == parent) continue;
    if (in[v] == -1) {
      edges.emplace_back(v, u);
      visit(v, edge_id);
      if (low[v] == in[v])
        ++bridges;
      low[u] = min(low[u], low[v]);
    } else {
      low[u] = min(low[u], in[v]);
    }
  }
  for (auto edge : graph[u]) {
    int v = edge.first;
    if (in[v] == low[u]) {
      edges.emplace_back(u, v);
      break;
    }
  }
}

void DFS() {
  for (int i = 0; i < edges.size(); ++i) {
    graph[edges[i].first].emplace_back(edges[i].second, i);
    graph[edges[i].second].emplace_back(edges[i].first, i);
  }
  edges.clear();
  for (int i = 0; i < N; ++i)
    in[i] = low[i] = -1;
  dfstime = 0;
  bridges = 0;
  for (int i = 0; i < N; ++i)
    if (in[i] == -1)
      visit(i, -1);
  for (int i = 0; i < N; ++i) {
    vector<pair<int, int>> temp;
    graph[i].swap(temp);
  }
}

const int MESSAGES = 20;

int main() {
  N = NumberOfIsles();
  M = NumberOfBridges();

  int from = MyNodeId() * (long long)M / NumberOfNodes();
  int to = (1 + MyNodeId()) * (long long)M / NumberOfNodes();
  for (int i = from; i < to; ++i)
    edges.emplace_back(BridgeEndA(i), BridgeEndB(i));

  int rounds = 1;
  while ((1 << (rounds - 1)) < NumberOfNodes())
    ++rounds;

  for (int round = 0; round < rounds; ++round) {
    if ((MyNodeId() & ((1 << round) - 1)) == 0) {
      // cerr << MyNodeId() << " works in round " << round << " ";
      DFS();
      if ((MyNodeId() >> round) & 1) {
        int target = MyNodeId() - (1 << round);
        // cerr << " and sends to " << target << endl;
        for (int message = 0; message < MESSAGES; ++message) {
          for (int i = message; i < edges.size(); i += MESSAGES) {
            PutInt(target, edges[i].first);
            PutInt(target, edges[i].second);
          }
          PutInt(target, -1);
          PutInt(target, -1);
          Send(target);
        }
      } else if (MyNodeId() + (1 << round) < NumberOfNodes()) {
        int source = MyNodeId() + (1 << round);
        // cerr << " and receives from " << source << endl;
         for (int message = 0; message < MESSAGES; ++message) {
           Receive(source);
           while (true) {
             int a = GetInt(source);
             int b = GetInt(source);
             if (a == -1 && b == -1)
               break;
             edges.emplace_back(a, b);
           }
         }
      }
    }
  }

  if (MyNodeId() == 0) { 
    cout << bridges << endl;
  }
  return 0;
}