#include <iostream> #include <vector> #include "sabotaz.h" #include "message.h" const int INFINITY = 100000000; int mostow=0; int * in; int * pi; int counter=1; using namespace std; vector<int> * mosty; int dfs(int x){ int answer = x; in[x]=counter++; for(int j=0; j< mosty[x].size(); j++){ int v = mosty[x][j]; if (v==x) continue; if (v==pi[x]) continue; if (in[v]==INFINITY){ pi[v] = x; v = dfs(v); } if (in[answer] > in[v]) answer=v; } if (answer==x && pi[x]!=x){ mostow++; //cout << x << " " << pi[x] << endl; } return answer; } int main() { if(MyNodeId()==0){ int n, m, a, b; in=new int[n]; pi=new int[n]; n=NumberOfIsles(); m=NumberOfBridges(); mosty = new vector<int>[n]; for(int i=0; i<m; i++){ a=BridgeEndA(i); b=BridgeEndB(i); if(a==b)continue; mosty[a].push_back(b); mosty[b].push_back(a); } for(int i=0; i<n; i++){ in[i]=INFINITY; } for(int i=0; i<n; i++){ if(in[i]==INFINITY){ pi[i]=i; dfs(i); } } cout << mostow; } 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 | #include <iostream> #include <vector> #include "sabotaz.h" #include "message.h" const int INFINITY = 100000000; int mostow=0; int * in; int * pi; int counter=1; using namespace std; vector<int> * mosty; int dfs(int x){ int answer = x; in[x]=counter++; for(int j=0; j< mosty[x].size(); j++){ int v = mosty[x][j]; if (v==x) continue; if (v==pi[x]) continue; if (in[v]==INFINITY){ pi[v] = x; v = dfs(v); } if (in[answer] > in[v]) answer=v; } if (answer==x && pi[x]!=x){ mostow++; //cout << x << " " << pi[x] << endl; } return answer; } int main() { if(MyNodeId()==0){ int n, m, a, b; in=new int[n]; pi=new int[n]; n=NumberOfIsles(); m=NumberOfBridges(); mosty = new vector<int>[n]; for(int i=0; i<m; i++){ a=BridgeEndA(i); b=BridgeEndB(i); if(a==b)continue; mosty[a].push_back(b); mosty[b].push_back(a); } for(int i=0; i<n; i++){ in[i]=INFINITY; } for(int i=0; i<n; i++){ if(in[i]==INFINITY){ pi[i]=i; dfs(i); } } cout << mostow; } return 0; } |