AtCoder Grand Contest #035 B問題 - Even Degrees

Source

AtCoder Grand Contest #035
問題文

問題概要

省略

解法

省略

cLay（version 20190714-1）のコード

C++に変換後のコードはこちら

int N, M, A[1d5], B[1d5];

int done[1d5];
int deg[1d5];
int st[1d5], sts;

int cur[1d5];
int C[1d5], D[1d5], ress;

void ade(int x, int y){
  C[ress] = x;
  D[ress++] = y;
  cur[x] ^= 1;
}

{
  int i, j, k;
  rd(N,M,(A--,B--)(M));
  graph g;
  unionFind uf;

  if(M%2){
    wt("-1");
    return 0;
  }

  uf.malloc(N);
  uf.init(N);
  k = M;
  M = 0;
  rep(i,k){
    if(uf(A[i],B[i])){
      A[M] = A[i];
      B[M++] = B[i];
    } else {
      ade(A[i], B[i]);
    }
  }
  
  g.setEdge(N, M, A, B);

  rep(i,N) deg[i] = g.es[i];
  rep(i,N) if(deg[i]==1) st[sts++] = i;

  while(sts){
    i = st[--sts];
    done[i] = 1;

    rep(j,g.es[i]){
      k = g.edge[i][j];
      if(done[k]) continue;
      deg[k]--;
      if(deg[k]==1) st[sts++] = k;

      if(cur[i]) ade(i,k);
      else       ade(k,i);
    }
  }

  rep(i,ress) wt(C[i]+1,D[i]+1);
}

Current time: 2024年04月24日03時42分50秒
Last modified: 2019年07月15日03時17分52秒 (by laycrs)
Tags: Competitive_Programming_Incomplete AtCoder AtCoder_Grand_Contest AGC035 AGC_B
トップページに戻る

Logged in as: unknown user (not login)