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 方向に操作を実施することはよくみる。