← C#

LESSON / EXERCISE

演習:参照関係からGCの回収対象を判定する

GCの到達可能性解析を簡略化したモデルで、ルートから到達できないオブジェクトを求めます。

演習:参照関係からGCの回収対象を判定する

簡略化したオブジェクト参照グラフが与えられます。ルートとして指定されたオブジェクトから参照をたどり、到達できないオブジェクトを求めてください。

入力

1行目にオブジェクト数 N と参照関係数 M。 続く M 行に参照元 u と参照先 v。 次の行にルート数 R。 最後の行に R 個のルートIDが空白区切りで与えられます。

オブジェクトIDは 1 から N です。

出力

1行目に到達不能なオブジェクト数 K。 2行目に到達不能なIDを昇順で出力してください。K が 0 の場合は2行目を空行にしてください。

制約

  • 1 <= N <= 200000
  • 0 <= M <= 300000
  • 1 <= R <= N

GCはルートから参照をたどって到達可能なオブジェクトを生存と判断します。この演習では、その到達可能性判定をグラフ探索で再現してください。

コード提出フォーム

CSHARP

安全なサーバー側採点連携が未接続のため、現在は提出できません。

採点基盤準備中