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; } |
English