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.
//algorytm na szukanie mostow pochodzi z "algorytmiki praktycznej" Piotra Sta�czyka #include "message.h" #include "sabotaz.h" #include <cstdio> //#include <iostream> #include <algorithm> //#include <string> #include <vector> using namespace std; typedef vector<int> VI; typedef long long LL; typedef vector<VI> VVI; typedef vector<LL> VLL; typedef vector<double> VD; //typedef vector<string> VS; typedef pair<int, int> PII; typedef vector<PII> VPII; #define PF push_front #define MP make_pair #define FOR(x, b, e) for(int x = b; x <= (e); ++x) #define FORD(x, b, e) for(int x = b; x >= (e); --x) #define REP(x, n) for(int x = 0; x < (n); ++x) #define VAR(v, n) typeof(n) v = (n) #define ALL(c) (c).begin(), (c).end() #define SIZE(x) ((int)(x).size()) #define FOREACH(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i) #define PB push_back #define ST first #define ND second template <class V, class E> struct Graph { struct Ed : E { int v; Ed(E p, int w) : E(p), v(w) { } }; struct Ve : V, vector<Ed> { }; vector<Ve> g; Graph(int n = 0) : g(n) { } void EdgeD(int b, int e, E d = E()) { g[b].PB(Ed(d, e)); } void EdgeU(int b, int e, E d = E()) { Ed eg(d, e); eg.rev = SIZE(g[e]) + (b == e); g[b].PB(eg); eg.rev = SIZE(g[eg.v = b]) - 1; g[e].PB(eg); } int s; VPII *X; void Bridges(VPII & res) { res.clear(); X = &res; s = 0; FOREACH(it, g) it->d = -1; REP(i, SIZE(g)) if (g[i].d == -1) BriSearch(i, -1); } void BriSearch(int v, int u) { g[v].d = g[v].low = s++; FOREACH(it, g[v]) { int w = it->v; if (g[w].d == -1) { BriSearch(w, v); if (g[w].low > g[v].d) { X->PB(MP(min(v, w), max(v, w))); } else g[v].low = min(g[v].low, g[w].low); } else if (w != u) g[v].low = min(g[v].low, g[w].d); } } }; struct vv { int d,low; }; struct ee { int rev; }; int main() { if(MyNodeId()) return 0; int i; // int n,m,a,b; // scanf("%d%d",&n,&m); Graph<vv,ee> gr(NumberOfIsles()); // Graph<vv,ee> gr(n); VPII k; int nob=NumberOfBridges(); //int nob=m; for(i=0;i<nob;++i) { // scanf("%d%d",&a,&b); // gr.EdgeU(a,b); gr.EdgeU(BridgeEndA(i),BridgeEndB(i)); } gr.Bridges(k); printf("%d",k.size()); 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 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 | //algorytm na szukanie mostow pochodzi z "algorytmiki praktycznej" Piotra Sta�czyka #include "message.h" #include "sabotaz.h" #include <cstdio> //#include <iostream> #include <algorithm> //#include <string> #include <vector> using namespace std; typedef vector<int> VI; typedef long long LL; typedef vector<VI> VVI; typedef vector<LL> VLL; typedef vector<double> VD; //typedef vector<string> VS; typedef pair<int, int> PII; typedef vector<PII> VPII; #define PF push_front #define MP make_pair #define FOR(x, b, e) for(int x = b; x <= (e); ++x) #define FORD(x, b, e) for(int x = b; x >= (e); --x) #define REP(x, n) for(int x = 0; x < (n); ++x) #define VAR(v, n) typeof(n) v = (n) #define ALL(c) (c).begin(), (c).end() #define SIZE(x) ((int)(x).size()) #define FOREACH(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i) #define PB push_back #define ST first #define ND second template <class V, class E> struct Graph { struct Ed : E { int v; Ed(E p, int w) : E(p), v(w) { } }; struct Ve : V, vector<Ed> { }; vector<Ve> g; Graph(int n = 0) : g(n) { } void EdgeD(int b, int e, E d = E()) { g[b].PB(Ed(d, e)); } void EdgeU(int b, int e, E d = E()) { Ed eg(d, e); eg.rev = SIZE(g[e]) + (b == e); g[b].PB(eg); eg.rev = SIZE(g[eg.v = b]) - 1; g[e].PB(eg); } int s; VPII *X; void Bridges(VPII & res) { res.clear(); X = &res; s = 0; FOREACH(it, g) it->d = -1; REP(i, SIZE(g)) if (g[i].d == -1) BriSearch(i, -1); } void BriSearch(int v, int u) { g[v].d = g[v].low = s++; FOREACH(it, g[v]) { int w = it->v; if (g[w].d == -1) { BriSearch(w, v); if (g[w].low > g[v].d) { X->PB(MP(min(v, w), max(v, w))); } else g[v].low = min(g[v].low, g[w].low); } else if (w != u) g[v].low = min(g[v].low, g[w].d); } } }; struct vv { int d,low; }; struct ee { int rev; }; int main() { if(MyNodeId()) return 0; int i; // int n,m,a,b; // scanf("%d%d",&n,&m); Graph<vv,ee> gr(NumberOfIsles()); // Graph<vv,ee> gr(n); VPII k; int nob=NumberOfBridges(); //int nob=m; for(i=0;i<nob;++i) { // scanf("%d%d",&a,&b); // gr.EdgeU(a,b); gr.EdgeU(BridgeEndA(i),BridgeEndB(i)); } gr.Bridges(k); printf("%d",k.size()); return 0; } |