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
| #include <iostream> #include <stdio.h> using namespace std; int par[50000],kin[50000]; void init(int n){ int i; for(i=0;i<n;i++){ par[i] = i; kin[i] = 0; } } void uniun(int xroot,int yroot,int x,int y,int o){ par[yroot] = xroot; kin[yroot] = (kin[x]-kin[y]-o+3)%3; } int find(int x){ if(par[x] == x)return x; int xroot; xroot = find(par[x]); kin[x] = (kin[par[x]]+kin[x]+3)%3; par[x] = xroot; return xroot; } int main(){ int n,k; int x,y,o; int count = 0; scanf("%d%d",&n,&k); init(n); while(k--){ scanf("%d%d%d",&o,&x,&y); x--; y--; if(x>=n||y>=n){ count++; continue; } int xroot = find(x); int yroot = find(y); if(xroot == yroot){ int u = (kin[x] - kin[y]+3)%3; if(u==0 && o == 1){ continue; } if(u == 1 && o == 2){ continue; } count++; }else{ uniun(xroot,yroot,x,y,o-1); } } printf("%d\n",count); return 0; }
|