2012年5月12日土曜日

GCJ2012 Round 1C Problem A. 問題紹介

Google Code Jam 2012 Round 1C
Problem A. Diamond Inheritance 問題紹介

オブジェクト指向言語の「クラス(class)」の継承関係を図にします(継承関係図みたいな)。
DBC を継承しています。BA を継承しています。CA を継承しています。
このとき、DA の関係を見ると、2つの異なる継承経路があります。(DBADCA

このような2つの異なる継承経路がある状態を Diamond Inheritance と呼び、与えられたクラスの継承関係の中に Diamond Inheritance があるかないかを調べるのが今回の問題です。

入力データ:
最初の行は問題数 T。以降 T問の問題データが続きます。
問題データの最初の行はクラスの数 N です。
その後1行1クラスで Nクラス分のデータが続きます。1行目が クラス1、2行目が クラス2…という具合。
各行は最初に継承しているクラスの数 M があり、その後スペース区切りで M個の継承しているクラスの番号(ID)が書かれています。

データ制限:
  • 1 ≤ T ≤ 50 (問題数50問)
  • Small input の場合:1 ≤ N ≤ 50 (最大50クラス)
    Large input の場合:1 ≤ N ≤ 1,000 (最大1,000クラス)
  • 0 ≤ Mi ≤ 10 (1つのクラスが継承するクラスは最大10クラス)

解き方はいずれ記事にします。
解いたコードはこちらにあります。

0 件のコメント:

コメントを投稿