Codeforces Round #285 DIV1 A問題/DIV2 C問題 - Misha and Forest

Source

Codeforces Round #285 DIV1 A問題
Codeforces Round #285 DIV2 C問題
Problem description

問題概要

$N$ ノードの無向グラフで森(つまり閉路がない)を考える.
具体的な枝の情報は与えられないが,各ノードに対する次数が与えられる.
また,各ノードに対して,そのノードに隣接するノードの番号のXORを取ったものが与えられる.
具体的にこのグラフに含まれる枝の本数と,各枝はどのノード間を結んでいるかを求める問題.
答えは存在することは保証されており,答えが複数あるならば何を出力しても良い.

解法

答えは一意に定まる(どの枝から出力するかなどは任意).
次数が $1$ のノードに着目すれば,そのノードがどのノードと繋がっているかは,XORの値を見ればわかる.
よって,枝が $1$ つ確定するので,その枝を取り除く(対応するノードの次数を $1$ 減らし,XORの値を更新する).
閉路がないので,それを繰り返せば,全ての枝が求まることになる.
次数が $1$ のノードを処理できるノードスタックやらキューやらに積んでおいて,それらを処理する.
途中で次数が $1$ になったノードも処理するノードスタックなどに詰め込む.
時間計算量は $O(N)$.

C++のスパゲッティなコード

#include<bits/stdc++.h>
using namespace std;

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define READER_BUF_SIZE 1048576
#define WRITER_BUF_SIZE 1048576
int reader_pt=READER_BUF_SIZE,reader_last;char reader_buf[READER_BUF_SIZE];
int writer_pt=0;char writer_buf[WRITER_BUF_SIZE];
#define mygc(c) {if(reader_pt==READER_BUF_SIZE)reader_pt=0,reader_last=fread(reader_buf,sizeof(char),READER_BUF_SIZE,stdin);(c)=reader_buf[reader_pt++];}
#define mypc(c) {if(writer_pt==WRITER_BUF_SIZE)writer_pt=0,fwrite(writer_buf,sizeof(char),WRITER_BUF_SIZE,stdout);writer_buf[writer_pt++]=(c);}
#define myed {fwrite(writer_buf,sizeof(char),writer_pt,stdout);writer_pt=0;}

void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
template <class T, class S> void reader(T *x, S *y){reader(x);reader(y);}

void writer(int x, char c){int s=0,m=0;char f[10];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}
template<class T> void writerLn(T x){writer(x,'\n');}
template<class T, class S> void writerLn(T x, S y){writer(x,' ');writer(y,'\n');}

int N;
int deg[1000000], s[1000000];
int ress, res1[1000000], res2[1000000];

int st[1000000], st_size;

int main(){
  int i, j, k;

  reader(&N);
  rep(i,N) reader(deg+i, s+i);

  rep(i,N) if(deg[i]==1) st[st_size++] = i;
  while(st_size){
    k = st[--st_size];
    if(deg[k] != 1) continue;

    i = k; j = s[k];
    res1[ress] = i;
    res2[ress] = j;
    ress++;

    deg[i]--;
    deg[j]--;
    s[i] ^= j;
    s[j] ^= i;
    if(deg[j]==1) st[st_size++] = j;
  }

  writerLn(ress);
  rep(i,ress) writerLn(res1[i],res2[i]);

  myed;
  return 0;
}

Current time: 2017年07月21日13時40分20秒
Last modified: 2015年01月16日07時15分20秒 (by laycrs)
Tags: Competitive_Programming Codeforces CF285 CF_Div1_A CF_Div2_C
トップページに戻る

Logged in as: unknown user (not login)

ログイン: