1131F - Asya And Kittens

1131F - Asya And Kittens

原 題: https://codeforces.com/problemset/problem/1131/F
題 意:

有 n 個 格 子，每 個 格 子 中 間 有 擋 板，給 你 n - 1 個 (x, y)，代 表 將 格 子裡 的 數 為 x 與 y 中 間 的 擋 板 拆 除 合 併 成 一 個 集 合。求 原 始 序 列，如 果 有 多 組 解 請 輸 出 任 意 一 種。

solve:
看 到 合 併 第 一 個 想 法 就 是 並 查 集，但 是 題 目 要 求 原 始 序 列。
我 想 說 既 然 有 相 鄰 的 關 係 那 會 不 會 是 紀 錄 合 併 的 順 序 ?
對 照 上 圖，假 如 現 在 合 併 (1, 4) 那 先 把 (1, 4) 裝 進 一 個 容 器，接 下 來 是 合 併 (2, 5)；一 樣 的 動 作，再 來 是 (3, 1) 但 是 1 已 經 屬 於 一 個 集 合 了，所 以 應 該 要 放 在 那 個 集 合 的 旁 邊 變 成 (1, 4, 3)，再 來 是 合 併 (4, 5)，兩 者 都 屬 於 不 同 集 合，所 以要 合 併 兩 者 並 且 讓 這 兩 個 集 合 相 鄰，變 成 (1 4 3 2 5)。

不 過 這 樣 的 容 器 code 難 度 有 點 高，所 以 我 又 想 了 一 下。如 果 把 並 查 集 的 "頭"當 樹 根；所 有 合 併 的 都 當 子 樹；再 從 樹 根 dfs 不 就 有 了 相 鄰 關 係?

結 論: 並 查 集 + dfs

code: