// Artur Kraska, II UWr #include <algorithm> #include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <vector> #include <cmath> #include <list> #include <set> #include <map> #include "sabotaz.h" #include "message.h" #define forr(i, n) for(int i=0; i<n; i++) #define FOREACH(iter, coll) for(typeof(coll.begin()) iter = coll.begin(); iter != coll.end(); ++iter) #define FOREACHR(iter, coll) for(typeof(coll.rbegin()) iter = coll.rbegin(); iter != coll.rend(); ++iter) #define lbound(P,R,PRED) ({typeof(P) X=P,RRR=(R), PPP = P; while(PPP<RRR) {X = (PPP+(RRR-PPP)/2); if(PRED) RRR = X; else PPP = X+1;} PPP;}) #define testy() int _tests; scanf("%d", &_tests); FOR(_test, 1, _tests) #define CLEAR(tab) memset(tab, 0, sizeof(tab)) #define CONTAIN(el, coll) (coll.find(el) != coll.end()) #define FOR(i, a, b) for(int i=a; i<=b; i++) #define FORD(i, a, b) for(int i=a; i>=b; i--) #define MP make_pair #define PB push_back #define deb(X) X; #define M 1000000007 #define INF 1000000007 using namespace std; int n, m, numer; long long res; struct ww { bool pa; int nr; int dss; int low; list <int> l; }; ww tab[200005]; void wczytaj() { int a, b; n = NumberOfIsles(); m = NumberOfBridges(); for(int i=0; i<m; i++) { a = BridgeEndA(i); b = BridgeEndB(i); tab[a].l.push_back(b); tab[b].l.push_back(a); } } void go(int v, int o) { tab[v].nr = tab[v].low = numer; numer++; int ile = 0; for(list<int>::iterator it = tab[v].l.begin(); it != tab[v].l.end(); ++it) { if(*it == o) { ile++; continue; } if(tab[*it].nr == 0) { go(*it, v); tab[v].low = min(tab[v].low, tab[*it].low); } else tab[v].low = min(tab[v].low, tab[*it].nr); } if(tab[v].low >= tab[o].nr) tab[o].pa = 1; if(tab[v].low > tab[o].nr) if(ile <= 1) res++;//, printf("most %d-%d\n", o, v); } void punkty_artykulacji() { int il = 0; numer = 2; tab[1].nr = tab[1].low = 1; for(list<int>::iterator it = tab[1].l.begin(); it != tab[1].l.end(); ++it) if(tab[*it].nr == 0) { go(*it, 1); il++; numer++; } tab[1].pa = il > 1; // for(int i=1; i<=n; i++) // printf("[%d] -> PA:%d\n", i, tab[i].pa); } int main() { if(MyNodeId() > 0) { return 0; } wczytaj(); punkty_artykulacji(); printf("%lld\n", res); 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 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 | // Artur Kraska, II UWr #include <algorithm> #include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <vector> #include <cmath> #include <list> #include <set> #include <map> #include "sabotaz.h" #include "message.h" #define forr(i, n) for(int i=0; i<n; i++) #define FOREACH(iter, coll) for(typeof(coll.begin()) iter = coll.begin(); iter != coll.end(); ++iter) #define FOREACHR(iter, coll) for(typeof(coll.rbegin()) iter = coll.rbegin(); iter != coll.rend(); ++iter) #define lbound(P,R,PRED) ({typeof(P) X=P,RRR=(R), PPP = P; while(PPP<RRR) {X = (PPP+(RRR-PPP)/2); if(PRED) RRR = X; else PPP = X+1;} PPP;}) #define testy() int _tests; scanf("%d", &_tests); FOR(_test, 1, _tests) #define CLEAR(tab) memset(tab, 0, sizeof(tab)) #define CONTAIN(el, coll) (coll.find(el) != coll.end()) #define FOR(i, a, b) for(int i=a; i<=b; i++) #define FORD(i, a, b) for(int i=a; i>=b; i--) #define MP make_pair #define PB push_back #define deb(X) X; #define M 1000000007 #define INF 1000000007 using namespace std; int n, m, numer; long long res; struct ww { bool pa; int nr; int dss; int low; list <int> l; }; ww tab[200005]; void wczytaj() { int a, b; n = NumberOfIsles(); m = NumberOfBridges(); for(int i=0; i<m; i++) { a = BridgeEndA(i); b = BridgeEndB(i); tab[a].l.push_back(b); tab[b].l.push_back(a); } } void go(int v, int o) { tab[v].nr = tab[v].low = numer; numer++; int ile = 0; for(list<int>::iterator it = tab[v].l.begin(); it != tab[v].l.end(); ++it) { if(*it == o) { ile++; continue; } if(tab[*it].nr == 0) { go(*it, v); tab[v].low = min(tab[v].low, tab[*it].low); } else tab[v].low = min(tab[v].low, tab[*it].nr); } if(tab[v].low >= tab[o].nr) tab[o].pa = 1; if(tab[v].low > tab[o].nr) if(ile <= 1) res++;//, printf("most %d-%d\n", o, v); } void punkty_artykulacji() { int il = 0; numer = 2; tab[1].nr = tab[1].low = 1; for(list<int>::iterator it = tab[1].l.begin(); it != tab[1].l.end(); ++it) if(tab[*it].nr == 0) { go(*it, 1); il++; numer++; } tab[1].pa = il > 1; // for(int i=1; i<=n; i++) // printf("[%d] -> PA:%d\n", i, tab[i].pa); } int main() { if(MyNodeId() > 0) { return 0; } wczytaj(); punkty_artykulacji(); printf("%lld\n", res); return 0; } |