読者です 読者をやめる 読者になる 読者になる

強連結成分分解においてどうしてスタックにあることを確かめる必要があるのか

強連結成分分解(SCC)を発見するTarjanアルゴリズムを学んでいたのですが、どうしてスタックにあるかどうかを確認する必要があるかがわからなかったのでその答えです。

答えを確かめるためにUVa 247を使いました。僕が解くために書いたソースコードは以下のとおりです。関節点で書いた記事と同じで、訪れたノードの順番をdfs_numに。子ノードから訪れることができる最小の親ノードの順番をdfs_lowに保存しています。

public static int[] dfs_num;
public static int[] dfs_low;
public static Stack<Integer> stack;
public static int[] inStack;
public static int dfs_counter;

public static void main(String[] args) {
  
  // Graphを隣接リストとして取得。変数名はadjList

  for (int i = 0; i < adjList.length; i++) {
    if (dfs_num[i] == 0) {
      solve(i);
    }
  }
}

public static void solve(int curr) {
  dfs_num[curr] = dfs_counter;
  dfs_low[curr] = dfs_counter;
  dfs_counter++;

  stack.push(curr);
  inStack[curr] = 1;
  ArrayList<Integer> edge = adjList[curr];

  for (int i = 0; i < edge.size(); i++) {
    int next = edge.get(i);
  
    if (dfs_num[next] == 0) {
      solve(next);
    }
    if (inStack[next] == 1) { // どうしてここのチェックが必要なのかがわからない。
      dfs_low[curr] = Math.min(dfs_low[curr], dfs_low[next]);
    }
  }

  if (dfs_num[curr] == dfs_low[curr]) {
    int pop = stack.pop();
    System.out.printf("SCC: (");
    while (pop != curr) {
      System.out.printf("%d ", pop);
      inStack[pop] = 0;
      pop = stack.pop();
    } 
    inStack[pop] = 0;
    System.out.printf("%d)\n", pop);
  }
}

どうして、スタックにあることを確かめる必要があるかはこういうテストケースを考えると理解できます。

f:id:ilovehugeworld:20170315101455p:plain

solveを呼ぶforループは0から始まるので、最初はノード0をチェックします。ノード0からいけるノードはないので再帰的にsolveを呼ぶことなく終了し、SCC (0)をプリントします。次にsolve(1)が呼ばれます。今回はエッジがあるのでforループに入り、問題のif文に来ます。もし、ここでif (inStack[next] == 1)がなければそのままノード0のdfs_low[0]の1を取得しdfs_low[1]に入れてしまいます。

そうすると、forループ後のdfs_num[curr] == dfs_low[curr]がtrueではなくなるため、SCC (1)をプリントしません。つもりこのif文は、今調べてるノードのdfs_low値を、すでに強連結されてるノードのdfs_lowで上書きしないためのif文だったのです。

逆にいうとnextが今調べてるノードと強連結する可能性がある時だけdfs_low[curr]をアップデートするという感じでしょうか。どうもわかりやすくできないかなと思ったのですが、何も思いつきませんでした。自分がきちんと実装できてるかを確かめるためにUVa 247を解いてみるといいかもしれません。

Podcast質問テンプレート

Podcastに興味を持っていただきありがとうございます。 こちらが現在用意してる質問のテンプレートです。コメントで聞きたいことを残していただければアップデートします。

[留学Podcast]

  • 留学した理由は?
  • 留学に対する準備は?(志望校選び、学部選び、資金、勉強の方法)
  • 今勉強してる内容は?
  • 何か思ってたことと違ったことはあった?
  • 友達どうやって作る?
  • 友達とどんなことして遊ぶ?
  • こういう人は留学にくるといいよ!
  • こういう人は留学オススメしないよ!

[海外就労Podcast]

  • 海外就労をしたいと思ったきっかけは?
  • したいと思ってからどのように準備した?
  • どうやって仕事を探した?
  • 勤務体系はどんな感じ?(お給料の相場観、休み、保険や早期退職、同僚とのコミュニケーション)
  • 日本との働き方と違うところは?
  • どうやってリフレッシュ/遊んでる?
  • こういう人は海外就労オススメだよ!
  • こういう人は海外就労オススメしないよ!

[雑談Podcast] フロリダ大学に通うSくん

RebuildFMBilingual Newsをよく聞いて楽しいので、自分もやってみたいと思いやってみました。

編集の粗が目立ちますが、次第によくなるのでご容赦ください。お相手はコミカレの時からの友達のS君と。転生したらスライムだった件の3万枚ページは400字の原稿用紙3万枚ページでした。暇な女子大生について話してるとき一部卑猥な言葉が含まれます。不快感を覚えられる方は10:04までスキップすることをオススメします。

追記 同日23:53:
友達から「これは違う。。。!!!」と猛烈なダメ出しを受けたので公開やめようと思いましたが、一応置いときます。「めっちゃストレスフルだった!!!!!」との感想なので、聞く場合は自己責任でお願いします。

ダメ出し:

  • テンポ悪い
  • 1時間長すぎ
  • 15分すぎた後からイライラしてくる
  • 水曜日の落ち込んだ話はいつしてるの?
  • 大まかなスクリプトあった方がよくない?
  • 妹の話大丈夫?(現在確認中。大丈夫でした。
  • 余計な音多い
  • 15分から始めてみたら
  • 個人情報出しすぎ
  • オーディエンス0www私聞いてるんだけどw
  • 当日いきなり声かけて撮った割にはいいんじゃない?
  • エンターテインメントになってない!!
  • 真面目な話をするのか、くだけた話をするのか決めて、真面目な話だったらコンピュータサイエンスのどこが楽しいか、つらいかを話すべき。砕けた内容だったらコンピュータサイエンスにいる女の子の特徴とか、良い点悪い点とか話すとかさ?
  • 留学系のPodcastやるんだったら、たくさんいるからもっと苦労した話とかカルチャーショックとかを面白おかしく話した方がいい。
  • 40分くらい聞いたのに何も得るものがなかった。ためになることが何もなかった。
  • トーンとか研究してみたら?あなたが聴いてるポッドキャストはきちんと編集してるよ。
  • これ途中でスキップできないの?10分くらいに
  • 携帯から聞くとスクロールバーがでない。(mp3プレイヤーを調べないといけないですね
  • 話題決めたほうがいいんじゃない?
  • あまりおもしろくない。よくわからない下ネタ。オーディエンス決めたほうがいい。
  • 編集が大事。YouTuberも編集の力が8割。バラエティの生放送とかグダグダだよ?芸人は守りに入るし、爆弾発言をしないために口数減らすし。あと、音声だけだから難しいよね
  • 孤独を感じてる人にとってはいいんじゃない?会話に参加してる感じする。
  • 目的がわからない。
  • あまり緊張してないのはいいんじゃない?

あと、僕に対する理解が深まったらしいです。と、まぁこんな感じでボロボロだったので聞く場合は本当に自己責任でお願いします

話した内容、簡略版
0:40 転生したらスライムだった件
07:05 暇な女子大生
10:04 Twitterと日本
15:06 炎上
20:45 昔の生活のほうが幸せ?
24:15 幸せて何?どんなとき感じる?
25:00 家に帰ってご飯を一緒に食べるのはすごい幸せ
26:20 理想の晩御飯シチュ
27:37 幸せに思うとき
29:45 近況
36:00 一緒にとったクラスの宿題の話
38:25 妹が暇な女子大生になっちゃう
40:38 RebuildfmとBilingual News
41:10 このPodcastで話す内容
42:07 トビタテ!留学Japan
43:46 カレンダーで一日終わったら丸でうめてく。
48:40 自分の成長をどうやって測るか
51:17 Podcastの方向性
53:16 ラジオにはまり始めた話
54:07 眠いの?
54:52 Sleepcycle
56:37 Sくんのi, j, k打てない携帯
57:17 昼寝しちゃう
59:26 でも、昼間眠い
1:05:40 ルームメイトがくさい問題
1:07:08 容量が足りずレコーディングが終わりました。長々とどうやってルームメイトに伝えるか問題について話しました。