#include<cstdio> #include<cstdlib> #include<cmath> #include<cstring> #include<cassert> #include<iostream> #include<algorithm> #include<queue> #include<stack> #include<bitset> #include<set> #include<map> #include "message.h" #include "sabotaz.h" #define REP(i,n) for(int i=0;i<(n);i++) #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 foreach(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();i++) #define all(c) (c).begin(),(c).end() #define scanf(...) scanf(__VA_ARGS__)?:0 #define eprintf(...) fprintf(stderr,__VA_ARGS__),fflush(stderr) #define e1 first #define e2 second #define mp make_pair #define pb push_back #define eb emplace_back using namespace std; typedef long long ll; typedef long double ld; typedef unsigned int uint; typedef unsigned long long ull; typedef pair<int,int> pii; typedef pair<ll,ll> pll; typedef pair<ll,int> pli; typedef pair<int,ll> pil; int inst,id,n,m,a,b,w,d[200001],ile[200001],pater[200001]; vector<int> v[200001]; bitset<200001> odw; void dfs(int a) { odw[a]=true; bool c=false; foreach(it,v[a]) if (!odw[*it]) pater[*it]=a,d[*it]=d[a]+1,dfs(*it),ile[a]+=ile[*it]; else if (d[*it]<d[a]) { if (*it==pater[a]) if (!c) c=true; else ile[a]++,ile[*it]--; else ile[a]++,ile[*it]--; } if (!ile[a]) w++; } int main() { inst=NumberOfNodes(); id=MyNodeId(); n=NumberOfIsles(); m=NumberOfBridges(); if (id==0) { REP(i,m) a=BridgeEndA(i),b=BridgeEndB(i),v[++a].pb(++b),v[b].pb(a); FOR(i,1,n) if (!odw[i]) dfs(i); printf("%d",w-1); } else eprintf("Kangurka jest wspaniala"); }
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 | #include<cstdio> #include<cstdlib> #include<cmath> #include<cstring> #include<cassert> #include<iostream> #include<algorithm> #include<queue> #include<stack> #include<bitset> #include<set> #include<map> #include "message.h" #include "sabotaz.h" #define REP(i,n) for(int i=0;i<(n);i++) #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 foreach(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();i++) #define all(c) (c).begin(),(c).end() #define scanf(...) scanf(__VA_ARGS__)?:0 #define eprintf(...) fprintf(stderr,__VA_ARGS__),fflush(stderr) #define e1 first #define e2 second #define mp make_pair #define pb push_back #define eb emplace_back using namespace std; typedef long long ll; typedef long double ld; typedef unsigned int uint; typedef unsigned long long ull; typedef pair<int,int> pii; typedef pair<ll,ll> pll; typedef pair<ll,int> pli; typedef pair<int,ll> pil; int inst,id,n,m,a,b,w,d[200001],ile[200001],pater[200001]; vector<int> v[200001]; bitset<200001> odw; void dfs(int a) { odw[a]=true; bool c=false; foreach(it,v[a]) if (!odw[*it]) pater[*it]=a,d[*it]=d[a]+1,dfs(*it),ile[a]+=ile[*it]; else if (d[*it]<d[a]) { if (*it==pater[a]) if (!c) c=true; else ile[a]++,ile[*it]--; else ile[a]++,ile[*it]--; } if (!ile[a]) w++; } int main() { inst=NumberOfNodes(); id=MyNodeId(); n=NumberOfIsles(); m=NumberOfBridges(); if (id==0) { REP(i,m) a=BridgeEndA(i),b=BridgeEndB(i),v[++a].pb(++b),v[b].pb(a); FOR(i,1,n) if (!odw[i]) dfs(i); printf("%d",w-1); } else eprintf("Kangurka jest wspaniala"); } |