AGC013-B:Hamiltonish Path

問題

https://beta.atcoder.jp/contests/agc013/tasks/agc013_b

N 頂点 M 辺の単純無向連結グラフが与えられる。以下の条件を満たすパスを構築してください。

  • 2 個以上の頂点を通る
  • 同じ頂点を 2 度通らない
  • パスの少なくとも一方の端点と直接辺で結ばれている頂点は、必ずパスに含まれる

制約

  • 2 <= N <= 10^5
  • 2 <= M <= 10^5
  • 2 <= A_i < B_i <= N

考え方

まず構築はサンプルは無視するのが基本。条件について考える。3つ目の条件「パスの少なくとも一方の端点と直接辺で結ばれている頂点は、必ずパスに含まれる」が重要。パスの端点になる頂点については、端点と隣接している頂点はパスに含まれる必要があるので、ある頂点から DFS したときにどこにも遷移できないような頂点が端点となる。

ある頂点から DFS を 2 度行って、それぞれどこにも遷移できなくなった頂点がパスの端点となる。

       public void solve(int testNumber, InputReader in, PrintWriter out) {

            int n = in.nextInt(), m = in.nextInt();
            List<Integer>[] g = new ArrayList[n];
            g = Stream.generate(ArrayList::new).limit(n).toArray(List[]::new);
            for (int i = 0; i < m; i++) {
                int a = in.nextInt()-1, b = in.nextInt()-1;
                g[a].add(b);
                g[b].add(a);
            }

            boolean[] used = new boolean[n];

            List<Integer> fore = new ArrayList<>();
            Deque<Integer> stack = new ArrayDeque<>();
            stack.add(0);
            used[0] = true;
            fore.add(0);
            while (!stack.isEmpty()) {
                int now = stack.remove();
                for (int next : g[now]) {
                    if (!used[next]) {
                        stack.add(next);
                        used[next] = true;
                        fore.add(next);
                        break;
                    }
                }
            }

            List<Integer> back = new ArrayList<>();
            stack.add(0);
            while (!stack.isEmpty()) {
                int now = stack.remove();
                for (int next : g[now]) {
                    if (!used[next]) {
                        stack.add(next);
                        used[next] = true;
                        back.add(next);
                        break;
                    }
                }
            }

            Collections.reverse(back);
            back.addAll(fore);

            out.println(back.size());
            for (int i = 0; i < back.size(); i++) {
                if (i > 0) {
                    out.print(" ");
                }
                out.print(back.get(i)+1);
            }
            out.print("\n");

        }

ポイント

  • どのような頂点が端点になりうるか考える
  • 構築はサンプルを捨てる

類題

雑記

グラフ上である頂点から 2 方向に操作を実施することはよくみる。