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
#include <cstdio>
#include <vector>
#include "sabotaz.h"
#include "message.h"
#include <algorithm>
using namespace std;

int ile_mostow = 0;
int num = 0;

void dfs_szukaj_mostow(int v, vector<vector<int> >& graf, vector<bool>& odwiedzony, vector<int>& preorder, vector<int>& low, int ojciec) {
    odwiedzony[v] = true;
    preorder[v] = num;
    low[v] = preorder[v];
    num++;
    for (int i = 0; i < graf[v].size(); ++i) {
        if (!odwiedzony[graf[v][i]]) {
            dfs_szukaj_mostow(graf[v][i], graf, odwiedzony, preorder, low, v);
            low[v] = min(low[v], low[graf[v][i]]);
        } else if (graf[v][i] != ojciec)
            low[v] = min(low[v], preorder[graf[v][i]]);
    }
    if (low[v] == preorder[v] && ojciec >= 0)
        ile_mostow++;
}

int main() {
    long long n = NumberOfIsles();
    long long m = NumberOfBridges();
    long long numOfNodes = NumberOfNodes();
    long long nodeId = MyNodeId();
    if (nodeId == 0) {
        vector<vector<int> > graf(n, vector<int>());
        for (int i = 0; i < m; ++i) {
            long long pocz = BridgeEndA(i);
	    	long long kon = BridgeEndB(i);
	    	graf[pocz].push_back(kon);
	    	graf[kon].push_back(pocz);
        }
        vector<bool> odwiedzony(n, false);
        vector<int> preorder(n, 0);
        vector<int> low(n, 0);
        for (int i = 0; i < n; ++i)
            if (!odwiedzony[i])
                dfs_szukaj_mostow(i, graf, odwiedzony, preorder, low, -1);
        printf("%d", ile_mostow);
    }
    return 0;
}