Help us understand the problem. What is going on with this article?

トポロジカルソートがわからなかったので調べてBFSで実装したのち、AtCoderの問題を解いてみた。

トポロジカルソート

実装できたけどワカッテハイナイ

トポロジカルソートとは

閉路がない有向グラフの各有向辺が順方向になるようにソートすること

有向非巡回グラフ(DAG)とは
DAGとは、有向グラフ且つ閉路のないグラフのことである。これは、ある操作の手順を表す時に用いられたりする。DAGはトポロジカルソートをすることができる。

参考サイト

トポロジカルソート
動的計画法によるトポロジカルソートの数え上げとπDDの構築
動的計画法入門
アルゴリズムとデータ構造

トポロジカルソートとは、下図のような木を順に並べたものらしい

※トポロジカルソートの結果は、複数存在する場合がある(図ではトポロジカルソートの結果として、423651と426135の二つを記載)

写真.png

  • 上図の423615という木を例に、並べる順としては以下のようになる
    1. どこにも依存していないものが一番左(4)
      1. 隣接リストを作成した段階で入次数(いりじすう と読むらしい)が0のものが根
    2. その次は、(4)のみに依存しているもの(2)
      1. (4)をリザルト用のListにaddし、(4)から(2)への辺を削除した結果、(2)の入次数は0になる
        1. (4)から(2)への辺を削除とは、「(4)をリザルトリストへaddする際に、(4)から他の頂点へののびている辺を隣接リストから探し、次の接続先の入次数をマイナスする」ことを指している。
    3. その次は、(2)のみに依存しているもの(3 または 6)
      1. (2)をリザルト用のListにaddし、(2)から(3)および(6)への辺を削除した結果、(3)および(6)の入次数は0になる
    4. その次は、(3) または (6)のみに依存しているもの([3]で(3)を選択しているなら(6)、[3]で(6)を選択しているなら、(2)のみに依存している(3)((6)と同列のもの)または(6)のみに依存している(1)または(5))
    5. 以下、全ての依存関係を確認していく

BFSで実装してみる

※実装したら下記のAOJのサイトで確認することができる
GRL_4_B | トポロジカルソート | グラフ | Aizu Online Judge

    private void solveA2() {
        int v = nextInt();
        int e = nextInt();

        /*
         *隣接リストの作成
         */
        List<List<Integer>> adj = new ArrayList<List<Integer>>();
        for (int i = 0; i < v; i++) {
            adj.add(new ArrayList<Integer>());
        }

        for (int i = 0; i < e; i++) {
            int from = nextInt();
            int to = nextInt();
            adj.get(from).add(to);
        }
        // 入次数が0のものを判定するための配列
        int indegree[] = new int[v];
        // 入次数0を判定
        for (int i = 0; i < v; i++) {
            List<Integer> temp = adj.get(i);
            //iをfromとするnode達
            for (int node : temp) {
                //入次数の個数
                indegree[node]++;
            }
        }

        /*
         * queueの作成
         * 入次数0のものをqueueに詰める
         * 入次数0から調査していく
         */
        ArrayDeque<Integer> q = new ArrayDeque<Integer>();
        for (int i = 0; i < v; i++) {
            if (indegree[i] == 0) {
                q.addLast(i);
            }
        }

        //訪問済み頂点数
        int cnt = 0;

        // トポロジカルソートの結果
        List<Integer> res = new ArrayList<Integer>();

        /*
         * BFS
         */
        while (!q.isEmpty()) {
            // 接続先の頂点を探索開始
            int u = q.removeFirst();
            //入次数0なのでリザルトにadd
            res.add(u);

            /*
             * この頂点の次の接続先の入次数を-する
             * その結果、入次数=0となる場合はソートリザルトに追加し、次の探索に利用する
             */
            for (int node : adj.get(u)) {

                indegree[node]--;
                if (indegree[node] == 0) {
                    q.addFirst(node);
                }
            }
            cnt++;
            if (cnt > v) {
                System.out.println("graph内に循環有");
                return;
            }
        }

        for (int i : res) {
            out.println(i);
        }
    }

AtCoderの問題を解いてみる

D - Restore the Tree

トポロジカルソートを使う問題ということでチャレンジしてみる

結論としては、トポロジカルソートのロジックをほぼ改変なしで解けた

写真 (1).png

  • 入力例 2 の構造は上記
    • 黒い辺が本来の木構造で、赤い辺はあとから足された辺
    • 元の木構造は「根以外の各頂点には、その親から一本の有向辺が伸びています」との記述があるので特定できる
  • トポロジカルソートで並べるときに、自分の入次数が0になる時(自分に向かっている辺を削除した時)の頂点が親(うまい言い回しがわからない。。。)
    • 例えば、隣接リストを作成した時の(1)の入次数は3
      • (1)への辺があるのは(4)(2)(6)だが、トポロジカルソートしていくと、
      • (4)(2)(6)の順で(1)への辺を削除していく
      • (6)→(1)の辺を削除した時に(1)への入次数は0になる
      • (1)への入次数が0になった時の(6)が自分の親となる(複数の親がいるときは、根から一番遠い親が元の木構造の時の親)

AtCoder:全国統一プログラミング王決定戦予選(D - Restore the Tree)

    private void solveA() {
        int v = nextInt();
        int e = nextInt();

        List<List<Integer>> rinsetuList = new ArrayList<List<Integer>>();

        for (int i = 0; i < v; i++) {
            rinsetuList.add(new ArrayList<Integer>());
        }

        int[] indegrees = new int[v];
        for (int i = 0; i < v - 1 + e; i++) {
            int from = nextInt() - 1;
            int to = nextInt() - 1;
            rinsetuList.get(from).add(to);
            indegrees[to]++;
        }

        ArrayDeque<Integer> queue = new ArrayDeque<Integer>();
        for (int i = 0; i < indegrees.length; i++) {
            if (indegrees[i] == 0) {
                queue.addLast(i);
            }
        }

        int[] par = new int[v];
        int cnt = 0;
        while (queue.size() != 0) {
            int index = queue.removeLast();

            for (Integer nextDegree : rinsetuList.get(index)) {
                int nextCnt = --indegrees[nextDegree];
                if (nextCnt == 0) {
                    queue.addLast(nextDegree);
                    par[nextDegree] = index + 1;
                }
            }
            if (cnt > v) {
                out.println("graph内に循環有");
                return;
            }
        }

        for (int i : par) {
            out.println(i);
        }

    }
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした