TopCoder SRM618 DIV1 EASY - Family

Source

TopCoder SRM618 DIV1 EASY (250pt)
Problem Statement

問題概要

ノード数 $N$ で各ノードの入次数(入ってくる枝の数)が $0$ または $2$ のDAG(閉路のない有向グラフ)が与えられる.
各枝について,始点のノードを親,終点のノードを子と呼ぶ.
つまり,各ノードは,親をちょうど $2$ つ持つか,親を持たないかのどちらか.
各ノードを男,女に分けることを考える.
ここで,親が $2$ つあるノードについて,$2$ つの親は違う性別でなければいけない.
このように,各ノードに男,女を振り分けることができるかどうかを判定する問題.

解法

同じ子供をもつ親は別の色に塗らないといけないとして,$2$ 彩色できるかを判定する.
それはDFSや,UnionFindで行うことができる.
($1$ 箇所適当に色を決めて,そこから色が決まる場所を全部決める.これを繰り返し,矛盾が生じなければ良い)

C++によるスパゲッティなソースコード

// #includeなどは略しています
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

void unionInit(int d[],int s){int i;rep(i,s)d[i]=i;}
int unionGet(int d[],int n){int t=n,k;while(d[t]!=t)t=d[t];while(d[n]!=n)k=d[n],d[n]=t,n=k;return n;}
int unionConnect(int d[],int a,int b){a=unionGet(d,a);b=unionGet(d,b);if(a==b)return 0;d[a]=b;return 1;}

class Family {
public:
string isFamily(vector <int> up1, vector <int> up2) {
  int i, j, k, n;
  int ind[210];

  n = up1.size();
  unionInit(ind, n*2);

  rep(i,n) if(up1[i] >= 0){
    j = up1[i];
    k = up2[i];
    unionConnect(ind, j, k+n);
    unionConnect(ind, k, j+n);
  }

  rep(i,n) if(unionGet(ind,i)==unionGet(ind,i+n)) return "Impossible";
  return "Possible";
}

}

Current time: 2017年09月25日11時37分17秒
Last modified: 2014年05月10日03時23分29秒 (by laycrs)
Tags: Competitive_Programming TopCoder Single_Round_Match SRM618 SRM_Div1_Easy
トップページに戻る

Logged in as: unknown user (not login)

ログイン: