[0]zero-index clytie0x/zero-index

27.2 DFS และส่วนเชื่อมต่อ

คำถามพื้นฐานที่สุดของกราฟคือ "จากจุดนี้ ไปถึงจุดไหนได้บ้าง" ถ้าตอบได้ ก็ตอบต่อได้ทันทีว่ากราฟแบ่งเป็นกี่กลุ่ม สองจุดอยู่กลุ่มเดียวกันไหม และกลุ่มนั้นมีวงจรหรือไม่ หน้านี้ตอบด้วย DFS (depth-first search) หรือการค้นแบบลึกก่อน ซึ่งก็คือ recursion จากบทที่ 9 กับการจดว่าไปที่ไหนมาแล้วแบบ state space ในหน้า 21.5 แล้วดูว่าทำไม DFS แบบ recursion พังกับกราฟใหญ่ และแก้ด้วย stack ของเราเอง

เดินลึกก่อน

ลองนึกถึงการเดินสำรวจถ้ำที่มีทางแยกเยอะ วิธีที่ไม่หลงคือ เดินเข้าทางแรกที่ยังไม่เคยไป ไปเรื่อยๆ จนสุดทาง แล้วถอยกลับมาทางแยกล่าสุดที่ยังมีทางที่ไม่เคยไปเหลืออยู่ และทำเครื่องหมายไว้ทุกจุดที่ผ่าน จะได้ไม่เดินวนซ้ำ

เขียนเป็นฟังก์ชัน dfs(v) ได้สามบรรทัด จดว่ามาถึง v แล้ว แล้วเรียก dfs กับเพื่อนบ้านทุกตัวที่ยังไม่เคยไป การถอยกลับเกิดเองตอนฟังก์ชันจบ เหมือน backtracking ในบทที่ 21 แต่ต่างกันตรงที่เครื่องหมาย ไม่ลบออก ตอนถอยกลับ เพราะจุดที่สำรวจจากตรงนี้ครบแล้ว มาจากทางไหนก็ได้ผลเท่าเดิม

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100001;
vector<int> adj[MAXN];
bool visited[MAXN];

void dfs(int v, int depth)
{
    visited[v] = true; // (1)!
    cout << string(2 * depth, ' ') << "visit " << v << '\n'; // (2)!
    for (int next : adj[v]) {
        if (!visited[next]) { // (3)!
            dfs(next, depth + 1);
        }
    }
}

int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1, 0);
    return 0;
}
  1. จดก่อนทำอย่างอื่น ถ้าย้ายไปจดหลังลูป เพื่อนบ้านจะเรียกกลับมาที่ v ซ้ำได้ระหว่างที่ v ยังไม่ถูกจด
  2. string(k, c) สร้างสตริงที่มีตัวอักษร c เรียงกัน k ตัว ตรงนี้คือช่องว่าง 2 × depth ตัว ไว้ย่อหน้าตามความลึก
  3. เช็กก่อนเรียก ถ้าไม่เช็ก จะเดินไปกลับระหว่างสองบ้านไม่รู้จบ ดูในส่วนลองทำให้พัง
9 9
1 2
1 4
2 3
2 5
4 5
5 6
3 6
7 8
8 9

visit 1
  visit 2
    visit 3
      visit 6
        visit 5
          visit 4

ย่อหน้าเท่ากับความลึกของการเรียก จาก 1 ไป 2 ก่อน เพราะ 2 อยู่ต้นรายการของ 1 แล้วลงลึกต่อไป 3 แล้ว 6 แล้ว 5 แล้ว 4 ยาวเป็นสายเดียว พอถึง 4 เพื่อนบ้านทุกตัวถูกจดแล้ว ฟังก์ชันจึงจบทีละชั้นย้อนกลับจนถึง 1 ซึ่งตอนนั้นเพื่อนบ้านอีกตัวคือ 4 ก็ถูกจดไปแล้ว ทุกจุดที่ไปถึงได้จากบ้าน 1 จึงถูกพิมพ์ ส่วนบ้าน 7 8 9 ไม่ถูกพิมพ์ เพราะไม่มีถนนต่อจากกลุ่มนี้

1 2 3 4 5 6 7 8 9 ไปไม่ถึง ลำดับ 1 ลำดับ 2 ลำดับ 3 ลำดับ 4 ลำดับ 5 ลำดับ 6

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

เวลาที่ใช้

เพราะมี visited แต่ละจุดเข้า dfs ได้ครั้งเดียว และในครั้งนั้นไล่รายการเพื่อนบ้านของตัวเองครั้งเดียว ผลรวมความยาวของทุกรายการคือ 2E งานทั้งหมดจึงเป็น O(V + E) ไม่ว่ากราฟจะมีวงจรมากแค่ไหน และไม่ว่าจะมีเส้นทางระหว่างสองจุดกี่แบบ ต่างจากการลองทุกเส้นทางที่จำนวนเส้นทางระเบิดได้แบบบทที่ 21

นับส่วนเชื่อมต่อ

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

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200001;
vector<int> adj[MAXN];
int group_of[MAXN];

void dfs(int v, int group)
{
    group_of[v] = group;
    for (int next : adj[v]) {
        if (group_of[next] == 0) {
            dfs(next, group);
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    int groups = 0;
    for (int v = 1; v <= n; v++) {
        if (group_of[v] == 0) { // (1)!
            groups++;
            dfs(v, groups);
        }
    }
    cout << "groups " << groups << '\n';
    for (int v = 1; v <= n; v++) {
        cout << group_of[v] << (v == n ? '\n' : ' ');
    }
    return 0;
}
  1. group_of ทำหน้าที่แทน visited ด้วย ค่า 0 แปลว่ายังไม่เคยไป จุดที่ถูก DFS ของกลุ่มก่อนหน้าไปถึงแล้วจะไม่เป็น 0 จึงไม่เปิดกลุ่มใหม่ซ้ำ
9 9
1 2
1 4
2 3
2 5
4 5
5 6
3 6
7 8
8 9

groups 2
1 1 1 1 1 1 2 2 2

ลูปข้างนอกวนครบ V จุด และ DFS ทุกครั้งรวมกันก็ยังไปแต่ละจุดครั้งเดียว ทั้งโปรแกรมจึงยังเป็น O(V + E) จุดที่ไม่มีถนนเลยก็นับเป็นกลุ่มหนึ่งที่มีสมาชิกคนเดียว

ถามว่าถึงกันไหม

บ้านสองหลังไปหากันได้ ก็ต่อเมื่ออยู่กลุ่มเดียวกัน เมื่อติดเลขกลุ่มเสร็จ แต่ละคำถามจึงตอบได้ใน O(1) แค่เทียบเลขกลุ่ม ตัวอย่างนี้รับ N M Q แล้วตามด้วยถนน และคำถาม Q บรรทัด

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200001;
vector<int> adj[MAXN];
int group_of[MAXN];

void dfs(int v, int group)
{
    group_of[v] = group;
    for (int next : adj[v]) {
        if (group_of[next] == 0) {
            dfs(next, group);
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, q;
    cin >> n >> m >> q;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    int groups = 0;
    for (int v = 1; v <= n; v++) {
        if (group_of[v] == 0) {
            groups++;
            dfs(v, groups);
        }
    }
    for (int i = 0; i < q; i++) {
        int a, b;
        cin >> a >> b;
        cout << (group_of[a] == group_of[b] ? "YES" : "NO") << '\n';
    }
    return 0;
}

9 9 4
1 2
1 4
2 3
2 5
4 5
5 6
3 6
7 8
8 9
1 6
4 9
9 7
3 3

YES
NO
YES
YES

คำถามสุดท้ายถาม 3 กับ 3 ซึ่งเป็นบ้านเดียวกัน ตอบ YES เพราะทุกบ้านอยู่กลุ่มเดียวกับตัวเอง วิธีตรงไปตรงมาคือทุกคำถามล้าง visited แล้ว DFS จาก a ใหม่ แล้วดูว่า b ถูกจดไหม ใช้เวลา O(V + E) ต่อคำถาม รวมเป็น O(Q(V + E))

วัดบนเครื่องเดียวกับหน้า 19.1 กราฟสุ่ม N = M = Q รันแต่ละแบบ 5 รอบ ยกเว้นวิธีตรงไปตรงมารัน 3 รอบ ตารางเป็นค่ากลาง

ข้อมูลวิธีCode::Blocks (-Wall)-O2
N = M = Q = 20000DFS ใหม่ทุกคำถาม O(Q(V + E))19.7 วินาที9.616 วินาที
ติดเลขกลุ่มครั้งเดียว O(V + E + Q)0.035 วินาที0.036 วินาที
N = M = Q = 100000ติดเลขกลุ่มครั้งเดียว0.131 วินาที0.101 วินาที

กราฟสุ่มที่มีถนนเท่ากับจำนวนบ้าน มีกลุ่มใหญ่กลุ่มหนึ่งที่กินบ้านส่วนมาก DFS แต่ละครั้งจึงเดินเป็นหมื่นจุด ทำสองหมื่นครั้งก็หลายร้อยล้านขั้น วิธีตรงไปตรงมาที่ N = 100000 ไม่ได้รัน เพราะงานมากกว่าแถวแรกราวยี่สิบห้าเท่า หลักคิดเดียวกับ prefix sum ในบทที่ 19 คือทำงานหนักครั้งเดียวก่อนเริ่มถาม แล้วตอบทุกคำถามจากผลที่เก็บไว้

ลึกได้กี่ชั้น

DFS แบบ recursion ลึกได้เท่าความยาวของสายที่มันเดินลงไป ถ้ากราฟเป็นเส้นตรง 1 - 2 - 3 - ... - N โปรแกรม components จะเรียกซ้อนกัน N ชั้น บนเครื่องที่เขียนเอกสารนี้ รันจาก PowerShell ค่าละ 10 ครั้ง ได้ผลดังนี้

N ของเส้นตรงCode::Blocks (-Wall)-O2
25,000ผ่านทั้ง 10 ครั้งผ่านทั้ง 10 ครั้ง
26,000พัง 7 ครั้ง ผ่าน 3 ครั้งผ่านทั้ง 10 ครั้ง
27,000 ถึง 50,000พังทุกครั้งผ่านทุกครั้ง
96,000พังทุกครั้งผ่านทั้ง 10 ครั้ง
98,000 100,000 และ 200,000พังทุกครั้งพังทุกครั้ง

ทุกครั้งที่พังได้ Process returned -1073741571 (0xC00000FD) คือ stack overflow แบบหน้า 9.1 แบบ Code::Blocks ลึกได้ราวสองหมื่นห้าพันชั้น ใกล้กับที่หน้า 26.3 วัดไว้กับต้นไม้ ส่วนแบบ -O2 ที่ลึกได้เกือบแสนชั้น ไม่ได้แปลว่า -O2 ทำให้ recursion ลึกขึ้นเสมอ ตัวเลขนี้ได้มาเพราะ g++ เอาเนื้อของ dfs ไปวางซ้อนไว้ในตัวมันเองหลายชั้น เรียกว่าการ inline การเรียกฟังก์ชันจริงจึงน้อยกว่าจำนวนจุดหลายเท่า ลองคอมไพล์โปรแกรมเดิมแบบ -O2 แล้วเติมแฟล็ก -fno-inline-functions ที่ห้าม inline เส้นตรง 26,000 จุดพัง 9 ใน 10 ครั้ง ลึกได้พอๆ กับแบบ Code::Blocks ส่วน count_size ในหน้า 26.3 และ DFS ของ topological sort ในหน้า 30.1 ซึ่งหน้าตาคล้ายฟังก์ชันนี้มาก แบบ -O2 ก็พังตั้งแต่ 26,000 ชั้น (วัดซ้ำค่าละ 10 ครั้ง พัง 8 ครั้งและ 10 ครั้งตามลำดับ)

compiler จะ inline หรือไม่ ขึ้นกับรูปของฟังก์ชัน แก้โค้ดไม่กี่บรรทัดตัวเลขของ -O2 ก็เปลี่ยนได้มาก จึงอย่าวางใจตัวเลขนี้ ให้ถือว่า recursion บนเครื่องน้องลึกได้ราว 25,000 ชั้นเหมือนกันทุกที่ ทั้งแบบ Code::Blocks และแบบ -O2 โจทย์ที่ให้ N ถึงสองแสนพังทั้งสองแบบอยู่แล้ว

กราฟไม่ต้องเป็นเส้นตรงก็ลึกได้ ลองกับกราฟสุ่ม N = M = 200000 DFS ลงไปลึกที่สุด 52,496 ชั้น แบบ Code::Blocks พังทุกครั้ง แบบ -O2 ผ่าน ถ้าทดสอบในเครื่องแค่แบบ -O2 จะไม่รู้ตัวเลย และ grader แต่ละที่ตั้งขนาด stack ไม่เท่ากัน หลักเดียวกับหน้า 9.1 คือ recursion ที่อาจลึกถึงหลักหมื่นชั้นให้เขียนเป็นลูป

DFS ด้วย stack ของเราเอง

หน้า 26.3 แก้ปัญหานี้กับต้นไม้ด้วย stack<int> ที่จองหน่วยความจำนอก stack ของโปรแกรม กราฟใช้วิธีเดียวกันได้ ต่างกันแค่ต้องจดว่าไปแล้วด้วย

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200001;
vector<int> adj[MAXN];
int group_of[MAXN];

void dfs(int start, int group)
{
    stack<int> waiting;
    waiting.push(start);
    group_of[start] = group; // (1)!
    while (!waiting.empty()) {
        int v = waiting.top(); // (2)!
        waiting.pop();
        for (int next : adj[v]) {
            if (group_of[next] == 0) {
                group_of[next] = group; // (3)!
                waiting.push(next);
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    int groups = 0;
    for (int v = 1; v <= n; v++) {
        if (group_of[v] == 0) {
            groups++;
            dfs(v, groups);
        }
    }
    cout << "groups " << groups << '\n';
    for (int v = 1; v <= n; v++) {
        cout << group_of[v] << (v == n ? '\n' : ' ');
    }
    return 0;
}
  1. จดตั้งแต่ตอนใส่ลง stack ไม่ใช่ตอนหยิบออก แต่ละจุดจึงถูกใส่ลง stack ไม่เกินครั้งเดียว stack ใหญ่สุดไม่เกิน V ช่อง
  2. หยิบตัวบนสุด ซึ่งเป็นตัวที่ใส่ล่าสุด จึงยังเดินลึกลงไปทางที่เพิ่งเจอก่อน
  3. เจอเพื่อนบ้านที่ยังไม่มีกลุ่ม ติดเลขกลุ่มแล้วใส่ลง stack ไว้ไปต่อทีหลัง
9 9
1 2
1 4
2 3
2 5
4 5
5 6
3 6
7 8
8 9

groups 2
1 1 1 1 1 1 2 2 2

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

ถ้างานต้องการลำดับแบบ recursion เป๊ะๆ วิธีในหน้า 26.3 ใช้กับกราฟตรงๆ ไม่ได้ เพราะต้นไม้ไม่มีทางวนกลับจึงไม่มี visited กราฟต้องเปลี่ยนสองจุด คือจดตอนหยิบออกแทนตอนใส่ และใส่เพื่อนบ้านจากท้ายรายการย้อนขึ้นมา เพื่อนบ้านตัวแรกในรายการจะอยู่บนสุดและถูกหยิบก่อน เหมือนที่ recursion เรียกตัวแรกก่อน

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100001;
vector<int> adj[MAXN];
bool visited[MAXN];

void dfs(int start)
{
    stack<int> waiting;
    waiting.push(start);
    while (!waiting.empty()) {
        int v = waiting.top();
        waiting.pop();
        if (visited[v]) { // (1)!
            continue;
        }
        visited[v] = true;
        cout << "visit " << v << '\n';
        for (int i = (int)adj[v].size() - 1; i >= 0; i--) { // (2)!
            int next = adj[v][i];
            if (!visited[next]) {
                waiting.push(next);
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1);
    return 0;
}
  1. จุดเดียวกันอาจถูกใส่ลง stack หลายครั้งจากเพื่อนบ้านคนละตัว ตัวที่หยิบออกมาทีหลังถูกจดไปแล้ว ข้ามไปเลย
  2. ไล่รายการจากตัวท้ายขึ้นมาตัวแรก ตัวแรกจึงถูกใส่ลง stack ล่าสุด และถูกหยิบออกก่อน
9 9
1 2
1 4
2 3
2 5
4 5
5 6
3 6
7 8
8 9

visit 1
visit 2
visit 3
visit 6
visit 5
visit 4

ได้ลำดับ 1 2 3 6 5 4 ตรงกับโปรแกรม dfs-order ข้างบน สิ่งที่ต้องแลกคือ stack เก็บซ้ำได้ ตอนหยิบบ้าน 1 ออก บ้าน 4 ถูกใส่ไว้ก้น stack แล้วบ้าน 5 ใส่บ้าน 4 ซ้ำอีกครั้ง ส่วนบ้าน 5 เองก็ถูกใส่สองครั้งจากบ้าน 2 และบ้าน 6 เส้นเชื่อมหนึ่งเส้นทำให้ใส่ได้ไม่เกินหนึ่งครั้ง เพราะจุดที่เป็นคนใส่ถูกจดไปแล้ว ปลายอีกฝั่งจึงใส่มันกลับไม่ได้ stack จึงยาวได้ถึงราว E ช่อง แทนที่จะไม่เกิน V ช่องแบบโปรแกรม components-stack แต่เวลายังเป็น O(V + E)

วัดบนเครื่องเดียวกับหน้า 19.1 รันแต่ละแบบ 5 รอบ ตารางเป็นค่ากลาง

กราฟวิธีCode::Blocks (-Wall)-O2
สุ่ม N = M = 200000recursionพังด้วย 0xC00000FD0.193 วินาที
stack ของเราเอง0.241 วินาที0.176 วินาที
เส้นตรง N = 200000recursionพังด้วย 0xC00000FDพังด้วย 0xC00000FD
stack ของเราเอง0.091 วินาที0.067 วินาที

ทั้งสองแบบเป็น O(V + E) เวลาจึงพอกัน ตัวเลขในตารางรวมการอ่านถนนสองแสนเส้นและพิมพ์เลขกลุ่มสองแสนตัวด้วย สิ่งที่ต่างจริงคือแบบหนึ่งพังกับข้อมูลที่ลึก อีกแบบไม่พัง โจทย์ที่ N เกินหมื่นให้ใช้แบบ stack หรือ BFS เป็นค่าเริ่มต้น

ตรวจวงจร

ในภาพ DFS tree ข้างบน เส้นประ 1-4 กับ 2-5 คือเส้นที่ตอนตรวจแล้วพบว่าปลายทางถูกจดไปแล้ว ในกราฟไม่มีทิศ เส้นแบบนี้มีได้สองกรณี กรณีแรกคือเส้นที่เพิ่งเดินมา เช่น ตอนอยู่ที่ 2 แล้วเห็น 1 ซึ่งเป็นจุดที่เรียก dfs(2) มา จุดนี้เรียกว่า พ่อ (parent) ใน DFS tree เส้นนี้ไม่ใช่วงจร กรณีที่สองคือปลายทางถูกจดแล้วและไม่ใช่พ่อ แปลว่ามีอีกทางที่ไปถึงจุดนั้นได้ สองทางรวมกันเป็นวงจร จึงต้องส่งพ่อไปกับ dfs ด้วย

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100001;
vector<int> adj[MAXN];
bool visited[MAXN];
bool found_cycle;
int houses, road_ends;

void dfs(int v, int parent)
{
    visited[v] = true;
    houses++;
    road_ends += adj[v].size(); // (1)!
    for (int next : adj[v]) {
        if (!visited[next]) {
            dfs(next, v);
        } else if (next != parent) { // (2)!
            found_cycle = true;
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    int groups = 0;
    for (int v = 1; v <= n; v++) {
        if (!visited[v]) {
            groups++;
            found_cycle = false;
            houses = 0;
            road_ends = 0;
            dfs(v, 0);
            cout << "group " << groups << ": " << houses << " houses " << road_ends / 2 << " roads ";
            cout << (found_cycle ? "cycle" : "no cycle") << '\n';
        }
    }
    return 0;
}
  1. นับไปพร้อมกันว่าในกลุ่มมีปลายถนนกี่ปลาย ถนนหนึ่งเส้นมีสองปลาย หารสองได้จำนวนถนนในกลุ่ม ใช้ในวิธีที่สองข้างล่าง
  2. ปลายทางถูกจดแล้ว และไม่ใช่จุดที่เพิ่งเดินมา แปลว่าเจอวงจร
9 9
1 2
1 4
2 3
2 5
4 5
5 6
3 6
7 8
8 9

group 1: 6 houses 7 roads cycle
group 2: 3 houses 2 roads no cycle

มีวิธีที่สองที่ไม่ต้องใช้พ่อเลย ดูจากจำนวนอย่างเดียว กลุ่มที่มี V จุดและถึงกันหมด ถ้าไม่มีวงจรก็คือต้นไม้ ต้องมีเส้นเชื่อม V - 1 เส้นพอดี ถ้ามีมากกว่านั้นมีวงจรแน่นอน กลุ่มแรกมี 6 บ้าน ถนน 7 เส้น เกิน 5 จึงมีวงจร กลุ่มที่สองมี 3 บ้าน ถนน 2 เส้นพอดี จึงไม่มี วิธีนี้ใช้กับ DFS แบบ stack หรือ BFS ได้ทันที เพราะแค่นับ ไม่ต้องรู้ว่าใครเป็นพ่อใคร

ทั้งสองวิธีใช้ได้กับกราฟไม่มีทิศที่ไม่มีถนนซ้ำและไม่มีถนนวนเข้าหาตัวเอง ถ้าโจทย์อนุญาตถนนซ้ำ ถนนสองเส้นระหว่าง u กับ v ก็เป็นวงจรแล้ว วิธีที่ใช้พ่อจะมองไม่เห็น ส่วนกราฟมีทิศต้องใช้วิธีอื่น เพราะลูกศรที่ชี้กลับไปหาจุดที่จดแล้วไม่ได้แปลว่าวนกลับมาได้เสมอ เรื่องนั้นจะเรียนพร้อมกับ topological sort ในบทที่ 30

ลองทำให้พัง

แบบที่ 1 ไม่เช็กว่าเคยไปแล้ว

ในโปรแกรม dfs-order ลบ if (!visited[next]) ออก เหลือแค่ dfs(next, depth + 1); ในลูป คอมไพล์ผ่านโดยไม่มีคำเตือน พอรันกับกราฟของหมู่บ้าน หน้าต่างดำพิมพ์รัวๆ

visit 1
  visit 2
    visit 1
      visit 2
        visit 1
          visit 2

บรรทัดยาวขึ้นเรื่อยๆ เป็นหมื่นบรรทัด แล้ว Code::Blocks ขึ้นว่า

Process returned -1073741571 (0xC00000FD)

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

แบบที่ 2 ตรวจวงจรโดยไม่สนพ่อ

เขียนการตรวจวงจรแบบตรงไปตรงมา ว่าเจอจุดที่จดแล้วเมื่อไรก็คือวงจร โดยไม่ส่งพ่อไปด้วย

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100001;
vector<int> adj[MAXN];
bool visited[MAXN];
bool found_cycle;
int houses, road_ends;

void dfs(int v)
{
    visited[v] = true;
    houses++;
    road_ends += adj[v].size();
    for (int next : adj[v]) {
        if (!visited[next]) {
            dfs(next);
        } else {
            found_cycle = true;
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    int groups = 0;
    for (int v = 1; v <= n; v++) {
        if (!visited[v]) {
            groups++;
            found_cycle = false;
            houses = 0;
            road_ends = 0;
            dfs(v);
            cout << "group " << groups << ": " << houses << " houses " << road_ends / 2 << " roads ";
            cout << (found_cycle ? "cycle" : "no cycle") << '\n';
        }
    }
    return 0;
}

9 9
1 2
1 4
2 3
2 5
4 5
5 6
3 6
7 8
8 9

group 1: 6 houses 7 roads cycle
group 2: 3 houses 2 roads cycle

กลุ่มที่สองเป็นเส้นตรง 7 - 8 - 9 แต่ได้ว่ามีวงจร เพราะตอนอยู่ที่ 8 แล้วไล่เพื่อนบ้าน เจอ 7 ซึ่งเป็นจุดที่เพิ่งเดินมาและถูกจดแล้ว ถนนทุกเส้นถูกมองเห็นจากทั้งสองปลาย ถ้าไม่ยกเว้นพ่อ ทุกกลุ่มที่มีถนนอย่างน้อยหนึ่งเส้นจะถูกตอบว่ามีวงจรหมด ชุดทดสอบที่มีแต่กราฟมีวงจรจะผ่าน จึงต้องทดสอบกับต้นไม้ด้วยเสมอ

สรุป

  • DFS จดจุดปัจจุบันว่าไปแล้ว แล้วไปต่อที่เพื่อนบ้านที่ยังไม่เคยไปทีละตัว เครื่องหมายไม่ลบตอนถอยกลับ ใช้เวลา O(V + E)
  • นับส่วนเชื่อมต่อด้วยการเริ่ม DFS จากทุกจุดที่ยังไม่มีกลุ่ม ติดเลขกลุ่มครั้งเดียวแล้วตอบว่าถึงกันไหมได้ใน O(1)
  • DFS แบบ recursion บนเครื่องที่เขียนเอกสารนี้ลึกได้ราวสองหมื่นห้าพันชั้น แบบ -O2 บางฟังก์ชันลึกได้มากกว่าเพราะการ inline ซึ่งขึ้นกับรูปของฟังก์ชัน อย่าวางใจ กราฟสองแสนจุดพังทั้งคู่ ใช้ stack ของเราเองหรือ BFS
  • DFS ด้วย stack จดตอนใส่ลง stack ลำดับต่างจากแบบ recursion แต่ได้กลุ่มเดียวกัน ถ้าต้องการลำดับเดียวกัน ให้จดตอนหยิบออกและใส่เพื่อนบ้านย้อนลำดับ ซึ่ง stack จะยาวได้ถึงราว E ช่อง
  • กราฟไม่มีทิศมีวงจรเมื่อเจอจุดที่จดแล้วซึ่งไม่ใช่พ่อ หรือเมื่อกลุ่ม V จุดมีเส้นเชื่อมมากกว่า V - 1 เส้น