Problem A. Diamond Inheritance 問題紹介
オブジェクト指向言語の「クラス(class)」の継承関係を図にします(継承関係図みたいな)。
D は B と C を継承しています。B は A を継承しています。C も A を継承しています。
このとき、D と A の関係を見ると、2つの異なる継承経路があります。(D→B→A、D→C→A)
このような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 件のコメント:
コメントを投稿