ปูพื้นฐาน

กราฟที่ทุกปมมีทางออกทางเดียว: รูปที่ล็อกไว้แล้ว จึงเดาโครงเฉลยได้ตั้งแต่อ่านโจทย์จบ

พอรู้ว่าแต่ละกลุ่มคือวงหนึ่งวงที่มีต้นไม้ห้อยอยู่ คำถามเรื่องเดินไกลเป็นพันล้านก้าวก็กลายเป็นการหารเอาเศษ บทนี้ให้ท่าปอกใบทิ้งที่สั้นกว่าและพลาดยากกว่าการไล่หาวงตรง ๆ

ปัญหาที่บทนี้แก้

โจทย์บางข้อให้ข้อมูลมาในรูป "แต่ละอันชี้ไปอีกอันเดียว" เช่น เกาะแต่ละเกาะมีสะพานออกไปเส้นเดียว คนแต่ละคนส่งของต่อให้อีกคนเดียว หรือแต่ละตำแหน่งกระโดดไปตำแหน่งเดียว กราฟแบบนี้เรียกว่า กราฟฟังก์ชัน (functional graph)

ข่าวดีคือกราฟแบบนี้มีรูปร่างตายตัว พอรู้รูปแล้ว โจทย์ที่ดูยากจะกลายเป็นเลขคณิตธรรมดา บทนี้จะให้รูปนั้น กับท่ามาตรฐานสองท่าที่ใช้กับมันได้เกือบทุกข้อ

รูปร่างที่ต้องเห็นในหัวก่อน

เดินตามลูกศรจากปมไหนก็ตาม เนื่องจากปมมีจำนวนจำกัด เราต้องเหยียบปมเดิมซ้ำสักวัน วันที่เหยียบซ้ำคือวันที่เข้าวง ดังนั้น

แต่ละกลุ่มของกราฟฟังก์ชันมีวงพอดีหนึ่งวง และที่เหลือคือต้นไม้ที่ห้อยลงมาจากปมบนวง

ท่าที่ 1 ปอกใบทิ้ง เพื่อหาว่าใครอยู่บนวง

ท่าที่คนคิดออกก่อนคือเดินตามลูกศรแล้วทำเครื่องหมาย แต่มันเขียนยากกว่าที่คิด เพราะต้องแยกให้ออกว่า ปมที่เจอซ้ำเป็นปมของรอบนี้หรือรอบก่อน ท่าที่สั้นกว่าและพลาดยากกว่าคือ ปอกใบทิ้ง

นับว่าแต่ละปมมีลูกศรชี้เข้ากี่เส้น ปมที่ไม่มีใครชี้เข้าเลยคือใบ ตัดทิ้งแล้วลดตัวนับของปมที่มันชี้ไป ทำซ้ำจนไม่มีใบเหลือ สิ่งที่ปอกไม่ออกคือปมบนวงพอดี เพราะปมบนวงมีเพื่อนบนวงชี้เข้าหาเสมอ

ลองเอง · เดินตามลูกศรให้ครบ k ก้าว

พอเจอคำถามที่ขอเป็นพันก้าว การกดทีละก้าวจะเริ่มไร้เหตุผล ลองคิดว่าอะไรที่ทำให้ข้ามทีเดียวหลายก้าวได้

ท่าที่ 2 เดิน k ก้าวโดยไม่เดินจริง

เมื่อรู้รูปแล้ว คำถามว่า "จากปม v เดิน k ก้าวไปโผล่ที่ไหน" ก็แตกเป็นสองกรณีที่ตอบได้ทันที

• ถ้า k ไม่เกินระยะจาก v ถึงวง คำตอบคือบรรพบุรุษลำดับที่ k ของ v ซึ่งอ่านจากเส้นทางที่เราถืออยู่ตอนเดินต้นไม้ได้เลย
• ถ้า k เกินระยะนั้น ก็หักระยะออกก่อน ที่เหลือคือการวนอยู่บนวง ซึ่งเป็นแค่การหารเอาเศษ ด้วยความยาววง

หลายคนจะนึกถึงตารางกระโดดที่เก็บว่าเดิน 1, 2, 4, 8 ก้าวไปไหน ซึ่งใช้ได้เหมือนกัน แต่กินหน่วยความจำ n log k ที่ n เป็นล้านและ k ถึง 10^18 ก็คือหกสิบเท่าของอาเรย์ ซึ่งมักเกินลิมิต ส่วนท่าข้างบนใช้หน่วยความจำแค่ไม่กี่อาเรย์

โจทย์ฝึกข้อที่ 1 · เดินตามลูกศร k ก้าวจากทุกปม

ให้ f ของทุกปมและเลข k ตอบว่าแต่ละปมเดิน k ก้าวแล้วไปอยู่ที่ปมไหน

เฉลยข้อที่ 1

// เดินตามลูกศร k ก้าวจากทุกปม โดย k ใหญ่ได้ถึง 10^18  ทำงานในเวลาเชิงเส้น
// แนวคิด: ปอกใบทิ้งเพื่อหาปมบนวง แล้วเดินต้นไม้ที่ห้อยอยู่โดยถือ "เส้นทางจากวงลงมาถึงตัวเอง" ไว้ในสแต็ก
// ก้าวที่ยังไม่ถึงวงตอบจากสแต็กได้ทันที ส่วนก้าวที่เลยวงไปแล้วเป็นแค่การหารเอาเศษ
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    int n; ll k;
    scanf("%d %lld", &n, &k);
    vector<int> f(n + 1), indeg(n + 1, 0);
    for (int i = 1; i <= n; i++) { scanf("%d", &f[i]); indeg[f[i]]++; }

    vector<int> peeled;
    for (int i = 1; i <= n; i++) if (!indeg[i]) peeled.push_back(i);
    for (size_t h = 0; h < peeled.size(); h++)
        if (--indeg[f[peeled[h]]] == 0) peeled.push_back(f[peeled[h]]);
    vector<char> onCyc(n + 1, 0);
    for (int i = 1; i <= n; i++) onCyc[i] = indeg[i] > 0;

    // ลูกของ v คือปมที่ชี้มาหา v และตัวมันเองไม่ได้อยู่บนวง
    vector<int> head(n + 1, -1), nxt(n + 1, -1);
    for (int i = 1; i <= n; i++)
        if (!onCyc[i]) { nxt[i] = head[f[i]]; head[f[i]] = i; }

    vector<int> ans(n + 1, 0);
    vector<char> done(n + 1, 0);
    vector<int> cyc, path;
    for (int s = 1; s <= n; s++) {
        if (!onCyc[s] || done[s]) continue;
        cyc.clear();
        for (int u = s; !done[u]; u = f[u]) { done[u] = 1; cyc.push_back(u); }
        ll c = (ll)cyc.size();
        for (ll i = 0; i < c; i++) ans[cyc[i]] = cyc[(i + k) % c];

        for (ll i = 0; i < c; i++) {                    // เดินต้นไม้ที่ห้อยจากปมบนวงตัวนี้
            path.assign(1, cyc[i]);
            vector<int> it(1, head[cyc[i]]);
            while (!path.empty()) {
                if (it.back() < 0) { path.pop_back(); it.pop_back(); continue; }
                int v = it.back();
                it.back() = nxt[v];
                path.push_back(v);
                ll d = (ll)path.size() - 1;             // ระยะจากปมบนวงลงมาถึง v
                if (k <= d) ans[v] = path[d - k];       // ยังไม่ถึงวง ตอบจากสแต็กได้เลย
                else ans[v] = cyc[(i + (k - d)) % c];   // เข้าวงแล้ว ที่เหลือคือเศษ
                it.push_back(head[v]);
            }
        }
    }
    for (int v = 1; v <= n; v++) printf("%d%c", ans[v], v == n ? '\n' : ' ');
}

โจทย์ฝึกข้อที่ 2 · นับปมที่อยู่บนวง

ให้ f ของทุกปม ตอบว่ามีปมกี่ปมที่อยู่บนวง

เฉลยข้อที่ 2

// นับว่ามีปมกี่ปมที่อยู่บนวง  ทำได้ด้วยการปอกใบทิ้งอย่างเดียว ไม่ต้องค้นหาวงเลย
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n; scanf("%d", &n);
    vector<int> f(n + 1), indeg(n + 1, 0);
    for (int i = 1; i <= n; i++) { scanf("%d", &f[i]); indeg[f[i]]++; }
    vector<int> q;
    for (int i = 1; i <= n; i++) if (!indeg[i]) q.push_back(i);
    for (size_t h = 0; h < q.size(); h++) if (--indeg[f[q[h]]] == 0) q.push_back(f[q[h]]);
    printf("%d\n", n - (int)q.size());           // ที่ปอกไม่ออกคือปมบนวงพอดี
}

ท่าที่ 3 · หาวงโดยไม่ต้องจดว่าเคยไปไหน

ท่าปอกใบในบทนี้หาว่าใครอยู่บนวงได้ครบ แต่มันต้องมีอาเรย์นับดีกรีและคิวขนาดเท่าจำนวนปม คือใช้หน่วยความจำ O(n) ซึ่งปกติไม่ใช่ปัญหา แต่มีสถานการณ์ที่มันเป็นปัญหาจริง คือตอนที่เราไม่มีกราฟทั้งใบอยู่ในมือ เรามีแค่ฟังก์ชันที่ถามได้ทีละก้าวว่า "จากตรงนี้ไปไหนต่อ" เช่นลำดับสุ่มที่คำนวณค่าถัดไปจากค่าปัจจุบัน

ในสถานการณ์นั้นยังหาวงได้ ด้วยหน่วยความจำคงที่ ไม่ขึ้นกับขนาดของวงเลย ท่านั้นชื่อ เต่ากับกระต่าย (tortoise and hare หรือเรียกตามชื่อคนคิดว่า Floyd)

เดินสองตัวพร้อมกันจากจุดเดียวกัน ตัวหนึ่งก้าวละหนึ่ง อีกตัวก้าวละสอง ถ้ามีวงอยู่ ตัวเร็วจะวนกลับมาไล่ตัวช้าทันในวงแน่ ๆ เพราะระยะห่างระหว่างสองตัวเพิ่มขึ้นทีละหนึ่งก้าว เมื่อทั้งคู่อยู่ในวงแล้ว ระยะห่างจึงต้องมาลงตรงศูนย์พอดีในที่สุด

จุดที่เจอกันยังไม่ใช่ปมแรกของวง แต่มันมีคุณสมบัติที่ใช้ต่อได้ คือระยะจากจุดเริ่มถึงปมแรกของวง เท่ากับระยะจากจุดที่เจอกันถึงปมแรกของวงพอดี จึงย้ายตัวหนึ่งกลับไปที่จุดเริ่ม แล้วเดินสองตัวพร้อมกันทีละก้าว จุดที่มาเจอกันครั้งนี้คือปมแรกที่อยู่บนวง จากนั้นวนรอบวงหนึ่งรอบก็ได้ความยาววง

// เต่ากับกระต่าย (Floyd): หาความยาวหางกับความยาววงบนกราฟฟังก์ชัน
// ด้วยหน่วยความจำคงที่ ไม่ใช้อาเรย์ visited เลย
// อินพุต: n start แล้ว nxt[0..n-1]
// เอาต์พุต: mu lambda  (mu = จำนวนก้าวจาก start ถึงปมแรกที่อยู่บนวง, lambda = ความยาววง)
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, start;
    if (scanf("%d %d", &n, &start) != 2) return 0;
    vector<int> nxt(n);
    for (int i = 0; i < n; i++) scanf("%d", &nxt[i]);

    // เฟส 1 หาจุดพบกันในวง เต่าเดินหนึ่งก้าว กระต่ายเดินสองก้าว
    int slow = nxt[start];
    int fast = nxt[nxt[start]];
    while (slow != fast) {
        slow = nxt[slow];
        fast = nxt[nxt[fast]];
    }
    // เฟส 2 ย้ายเต่ากลับจุดเริ่ม แล้วเดินพร้อมกันทีละก้าว จุดที่เจอกันคือปมแรกบนวง
    int mu = 0;
    slow = start;
    while (slow != fast) {
        slow = nxt[slow];
        fast = nxt[fast];
        mu++;
    }
    // เฟส 3 วนรอบวงหนึ่งรอบ นับความยาว
    int lambda = 1;
    fast = nxt[slow];
    while (fast != slow) {
        fast = nxt[fast];
        lambda++;
    }
    printf("%d %d\n", mu, lambda);
    return 0;
}

// ตัวตรวจอิสระของเต่ากับกระต่าย: เดินไปเรื่อย ๆ แล้วจดว่าเคยเหยียบปมไหนตอนก้าวที่เท่าไร
// ใช้หน่วยความจำ O(n) ซึ่งเป็นสิ่งที่ท่าเต่ากระต่ายพยายามเลี่ยง จึงเป็นการตรวจที่อิสระจริง
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, start;
    if (scanf("%d %d", &n, &start) != 2) return 0;
    vector<int> nxt(n);
    for (int i = 0; i < n; i++) scanf("%d", &nxt[i]);

    vector<int> seenAt(n, -1);
    int cur = start, step = 0;
    while (seenAt[cur] == -1) {
        seenAt[cur] = step++;
        cur = nxt[cur];
    }
    int mu = seenAt[cur];              // ก้าวแรกที่เหยียบปมที่วนซ้ำ คือความยาวหาง
    int lambda = step - seenAt[cur];   // ก้าวที่เดินไปแล้วลบก้าวที่เคยเหยียบ คือความยาววง
    printf("%d %d\n", mu, lambda);
    return 0;
}

เกณฑ์เลือกระหว่างสองท่าชัดมาก ถ้ามีกราฟทั้งใบอยู่ในมือและต้องรู้ว่าทุกปมอยู่บนวงหรือไม่ ให้ปอกใบ เพราะรอบเดียวได้คำตอบของทุกปม ถ้ามีแค่ฟังก์ชันที่เดินได้ทีละก้าวและสนใจวงที่ปมเดียว เดินไปเจอ ให้ใช้เต่ากับกระต่าย เพราะไม่ต้องจองหน่วยความจำตามขนาดของสิ่งที่มองไม่เห็น

เอาไปใช้ที่ไหนในคลังนี้

• เส้นทางที่ยาวที่สุดบนเกาะ ใช้ท่าปอกใบทิ้ง แล้วต่อด้วยหน้าต่างเลื่อนบนวง เป็นตัวอย่างที่สมบูรณ์ที่สุดของบทนี้
• เครื่องเคลื่อนย้ายมวลสาร กราฟฟังก์ชันของมันเป็นการสลับที่ ซึ่งเป็นกรณีพิเศษที่ทุกปมมีลูกศรเข้าเส้นเดียวด้วย ทำให้ไม่มีต้นไม้ห้อยเลย มีแต่วงล้วน ๆ

สรุปบรรทัดเดียว

เมื่อทุกปมมีทางออกทางเดียว รูปของกราฟถูกล็อกไว้แล้วคือวงหนึ่งวงต่อกลุ่มพร้อมต้นไม้ที่ห้อยลงมา หาปมบนวงด้วยการปอกใบทิ้ง แล้วคำถามเรื่องการเดินไกล ๆ ก็กลายเป็นการหารเอาเศษ